44
votes
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.2k
42
votes
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.1k
36
votes
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 ...
- 80.2k
27
votes
Accepted
Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)
Generally speaking, the following is true for any algorithm:
Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $...
- 1,635
24
votes
Proof Complexity of a Proof or Disproof of P = NP
Proof complexity only makes sense when there is a sequence of statements depending on a parameter $n$. For example, the proposition $\mathsf{PHP}_n$ states (informally) that there is no bijection $[n+...
- 270k
23
votes
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.1k
22
votes
Accepted
Evolving artificial neural networks for solving NP problems
No. This direction is unlikely to be useful, for two reasons:
Most computer scientists believe that P $\ne$ NP. Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to ...
D.W.♦
- 141k
20
votes
Accepted
Is determining if there is a prime in an interval known to be in P or NP-complete?
So your problem is as follows:
Input: integers $\ell,u$
Question: does there exist a prime in $[\ell,u]$?
As far as I know, it is not known whether that problem is in P or not.
Here's what I do know:
...
D.W.♦
- 141k
19
votes
Accepted
NP-complete problems not "obviously" in NP
There are at least four such $NP$-complete problems listed in the appendix of Garey and Johnson's COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness.
[AN6] NON-DIVISIBILITY OF A ...
- 7,843
19
votes
Accepted
Is Post Correspondence Problem in NP?
The Post correspondence problem is undecidable, and in particular it is not in NP. The reason that your idea doesn't work is that the witness is not necessarily of polynomial size (in fact, you just ...
- 270k
17
votes
Is the class NP closed under complement?
First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science.
If $\sf P= NP$, ...
- 11.9k
17
votes
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 ...
D.W.♦
- 141k
17
votes
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....
- 270k
16
votes
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, ...
- 270k
15
votes
What does the 2 in a 2-approximation algorithm mean?
Typically, we use $\alpha < 1$ for maximization problems, and $\alpha > 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a ...
- 22.1k
15
votes
Accepted
Why are NP-complete problems so different in terms of their approximation?
One reason that we see different approximation complexities for NP-complete problems is that the necessary conditions for NP-complete constitute a very coarse grained measure of a problem's complexity....
- 17.7k
15
votes
Accepted
Does every problem in NP have an exponential time algorithm?
Yes, every NP problem has an exponential-time algorithm. One definition of NP is the "succinct certificates" definition: a language $L$ is in NP if, and only if, there is a relation $R$ on ...
- 80.2k
15
votes
Accepted
Can any finite problem be in NP-Complete?
If a finite problem is NP-complete then P=NP, since every finite problem has a polynomial time algorithm (even a constant time algorithm).
When we say that Sudoku is NP-complete, we mean that a ...
- 270k
15
votes
There are pretty much no algorithms in P
Actually you're wrong. In the example you give, you take a list of integers, but even with binary representation for the numbers in the list, the input length is still linear in the number of elements ...
- 311
14
votes
Why are NP-complete problems so different in terms of their approximation?
One way to consider the difference between decision version and optimization version is by considering different optimization versions of the same decision version. Take for example the MAX-CLIQUE ...
- 270k
14
votes
Accepted
Proof Complexity of a Proof or Disproof of P = NP
It is known that any proof of super-polynomial circuit lower bounds (which are slightly stronger statements than $P\neq NP$) require super-polynomial, even exponential size proofs in weak proof ...
- 408
13
votes
Accepted
Why does the solution of an NP problem have to be polynomial size?
First, let's refresh the proof that the definition given is indeed equivalent to the standard definition of NP, i.e., the class of languages accepted by polynomial-time nondeterministic Turing ...
- 80.2k
13
votes
How do we know any problem is in NP-complete if we don't know all problems in NP?
We do know all problems in NP. Each problem in NP is given by a non-deterministic Turing machine running in polynomial time. Steve Cook (and, independently, Leonid Levin) proved that SAT is NP-...
- 270k
13
votes
Accepted
Problem A is polynomially reducible to problem B... what can we say about A and B?
Your intuition about "relative hardness" is correct, the underlying mathematics is why III. is true. However your justification about I. is a little off (not wrong, but the reasoning is possibly not ...
- 17.7k
13
votes
Accepted
What do we know about NP ∩ co-NP and its relation to NPI?
The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in ...
- 270k
13
votes
Can a subset of an NP-complete problem be in P?
In fact, you don't need the P$\,\neq\,$NP hypothesis, since there are even infinite constant-time decidable subsets of NP-complete problems. For any NP-complete language $L\subseteq\{0,1\}^*$, let $L'...
- 80.2k
12
votes
NP Problems with unique solution
Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US.
UP: If $x \in L$, then there is exactly one "proof" ("witness", "...
- 4,009
12
votes
Accepted
Give a specific case where calling a polynomial time function n times gives an exponential time algorithm
A concrete example is repeated squaring. Squaring an integer of length $n$ takes time $O(n^2)$ (using the naive algorithm; you can do much better with more complicated algorithms). If you square an $n$...
- 270k
12
votes
Accepted
An one-sentence proof of P ⊆ NP
Since L is in P, you can answer the word problem in polynomial time. To show that L is in NP as well, we need to provide a polynomial checking relation $R$ such that
$$ w\in L \Leftrightarrow \exists ...
- 5,900
12
votes
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 (...
- 25.2k
Only top scored, non community-wiki answers of a minimum length are eligible