Theory and Algorithms Research

What is a decision problem?

A decision problem is an algorithmic problem that can be expressed as a yes-or-no query to an input value.


What does it mean for a decision problem to be decidable?

A decision problem is decidable when it can be resolved in a finite amount of steps by an algorithm that stops on all inputs.


What is the class P? What is the class NP?

Class P is a group of problems that can be resolved by a deterministic computer in polynomial time and require a "yes" or "no" response. (P stands for Polynomial Time)

Class NP is the set of decision problems that can be resolved in polynomial time by a non-deterministic machine. (NP stands for Non-deterministic Polynomial Time).


What is the intuitive meaning of the “P versus NP” question?

In the P vs NP problem, the question of whether every NP problem has a P solution or whether there are some NP problems that can't possibly be solved in P is raised. Although it appears evident, there is no formal mathematical proof that P does not equal NP.


If you resolve the P versus NP question, how much richer will you be?

A million dollars richer (Mandelbaum, 2019)


References

Accelerator, A. (2023). Decision Problem | The Most Up-to-Date Encyclopedia, News, Review & Research. Academic Accelerator. https://academic-accelerator.com/encyclopedia/decision-problem

decidable problem. (n.d.). https://xlinux.nist.gov/dads/HTML/decidableProblem.html

Explained: P vs. NP. (2009, October 29). MIT News | Massachusetts Institute of Technology. https://news.mit.edu/2009/explainer-pnp

GeeksforGeeks. (2023). Types of Complexity Classes P NP CoNP NP hard and NP complete. GeeksforGeeks. https://www.geeksforgeeks.org/types-of-complexity-classes-p-np-conp-np-hard-and-np-complete/

Mandelbaum, R. F. (2019, July 3). If You Solve This Math Problem, You Could Steal All the Bitcoin in the World. Gizmodo. https://gizmodo.com/if-you-solve-this-math-problem-you-could-steal-all-the-1836047131