# Tag Info

### Ackermann Decision Problem

No, you don’t need to compute the Ackerman function to verify this at all. The problem is trivial for x <= 3. And for x >= 4, if you can write down y, then the answer is “no”.
• 27.1k

### I would like to know what are the directions to work on if I want to prove that $NP=coNP$?

There are no directions that are likely to be accessible to an amateur. The problem is believed to be extremely hard. No one knows of any directions that are believed to be very promising. Instead, ...
• 150k
1 vote
Accepted

### The extent of NP-Completeness

Yes and no, even if we assume P $\not=$ NP was not proven. It depends on how someone "solved" the traveling salesman problem. If someone constructed a polynomial-time algorithm that solves ...
• 37.3k
Accepted

### Complexity of this variant of $⊕2SAT$?

This problem can be solved easily: trivially, the number of solutions is 0, so the parity is even. Consider any other variable $b$. Then because the formula $\varphi$ must contain all clauses that ...
• 150k
Accepted

### Non rigorous argument that $P \ne NP$ implies $avgP \ne distNP$

Let $X$ be the chosen subset of inputs to which we can restrict 3-SAT such that algorithm A remains superpolynomial. Then no algorithm A’ that solves 3-SAT’ can run in polynomial time on average ...
• 7,258
Accepted

### How is the Subset Sum Problem NP-Complete?

The subset sum problem can easily be solved in polynomial time in the number of items, and the sizes of the items. However, to be in NP, the solution must be in polynomial time in the problem size. ...
• 27.1k

### Are there any other language classes of time complexity between the P language class and the NP language class?

PMar's answer is correct. Having said that, there are several language classes "between" $P$ and $NP$. An example is $RP$, the class of languages accepted in randomised polynomial time. A ...
• 19.8k

### Difference between function and search problems?

$\mathrm{PPAD}$ is a class of search problems, not of function problems. The notion of search problem is more general than that of function problem, which in turn is more general than a decision ...
• 2,556