# Tag Info

### Is there a task that is solvable in polynomial time but not verifiable in polynomial time?

This is only possible if there are many admissible outputs for a given input. I.e., when the relation $R$ is not a function because it violates uniqueness. For instance, consider this problem: ...
• 14.6k
Accepted

### Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

There are two cases: $P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded ...
• 29.8k
Accepted

### How is the traveling salesman problem verifiable in polynomial time?

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances. The class of problems where you can verify "no" instances in polynomial ...
• 81.7k
Accepted

• 277k

### Can a subset of an NP-complete problem be in P?

Your question doesn't make sense: The problem is NP-complete (proven) for all input data (without exception). This is not a thing. NP-completeness is a property of entire sets, not of specific ...
• 29.8k
Accepted

### Why is Integer Linear Programming in NP?

As you have seen in other sources, the proof that there exists a witness with polynomial size does not exactly fit inside the margin, so to speak. The proof I know of (from the book I mention below) ...
• 8,248

### False proofs that look correct

One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy_or_Girl_paradox I tell it as I learned it*, as follows: in a village, each family has two children, elder ...
• 17.2k
Accepted

### Is detecting easy instances of NP-hard problems easy?

The problem isn't really well-posed. For any particular instance, there is a single solution, say $S$. Consequently, we can imagine an algorithm that has the answer $S$ hardcoded in: no matter what ...
• 159k
Accepted

### Why rectangle packing is NP-hard but maybe not in NP?

In order for a language $L$ to be in NP, there needs to be a way to certify that instance $x$ belongs to $L$. This "way" is a polynomial size witness which can be verified in polynomial time....
• 277k
Accepted

### is FIND WORDS in P?

Your language is in P. Suppose that the matrix is $n\times n$ and that the words have total length $\ell$. Each word can start at at most $n^2$ positions and be written in $O(1)$ many orientations, ...
• 277k

• 5,951
Accepted

### If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

Your prof was absolutely not rigorous (i.e. completely wrong), that's why the distinction between NP and co-NP doesn't make sense with his definition. Better definition: Def.: A decision problem (...
• 30k