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: ...
chi's user avatar
  • 14.6k
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 ...
Joey Eremondi's user avatar
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 ...
David Richerby's user avatar
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 $...
lox's user avatar
  • 1,669
26 votes

Why are computability problems always written in full caps?

After the Cook-Levin Theorem Richard Karp realized that the complexity of computational problems could be compared. His paper was prepared in a type-writer font, and used underlining and all-caps for ...
Hendrik Jan's user avatar
  • 30.6k
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+...
Yuval Filmus's user avatar
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 ...
Joey Eremondi's user avatar
19 votes
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) ...
Discrete lizard's user avatar
  • 8,248
18 votes

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 ...
Shaull's user avatar
  • 17.2k
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.'s user avatar
  • 159k
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....
Yuval Filmus's user avatar
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, ...
Yuval Filmus's user avatar
16 votes

False proofs that look correct

Merge-sort can be done in linear time! Indeed, the time complexity to sort a list or array of length $n$ verifies$^{(1)}$: $$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\...
Nathaniel's user avatar
  • 15.6k
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 ...
Yuval Filmus's user avatar
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 ...
Felix's user avatar
  • 311
14 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$...
Yuval Filmus's user avatar
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 ...
Jan Johannsen's user avatar
14 votes

Why are computability problems always written in full caps?

In the area of discrete mathematics, sets are usually typeset in capital letters. The above problem classes are sets of problems, e.g. SAT is the set of all boolean satisfiability problems. Thus, the ...
Per Alexandersson's user avatar
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'...
David Richerby's user avatar
12 votes
Accepted

How can I show that the Cook-Levin theorem does not relativize?

Please refer Does Cook Levin Theorem relativize?. Also refer to Arora, Implagiazo and Vazirani's paper: Relativizing versus Nonrelativizing Techniques: The Role of local checkability. In the paper ...
Sarvottamananda's user avatar
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 ...
adrianN's user avatar
  • 5,951
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 (...
gnasher729's user avatar
12 votes

Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

Actually, your version is correct and Wikipedia's is wrong! (Except that it has a tiny disclaimer at the bottom.) If $\mathrm{P}=\mathrm{NP}$, Wikipedia claims that every problem in $\mathrm{P}$ is $\...
David Richerby's user avatar
12 votes

A problem in NP but not NP-complete?

As written, the question is a bit trivial: if NP = NP-complete, then since P $\subseteq$ NP we get P=NP since every problem in P would be NP-complete. I suspect what's meant, though, is the following:...
Noah Schweber's user avatar
11 votes
Accepted

Why are Chess, Mario, and Go not NP-complete?

It's a common misconception that chess is NP-hard. Generalized chess may be NP-hard. Chess has an 8x8 board, generalized chess has an nxn board with many pieces. The question then becomes if ...
Albert Hendriks's user avatar
11 votes

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

If P=NP, that means there is for any given problem in NP, for example, the problem "Is $G$ $k$-colourable?", where $G$ is a finite graph and $k$ an integer, there is an algorithm to solve it in ...
Especially Lime's user avatar
11 votes
Accepted

Are there problems in NP that do not reduce in polynomial time to any problem in NP?

I understand the question as asking for the truth value of the proposition $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP}, A \not\le_p B$, where $\le_p$ denotes Karp reducibility. Then the ...
Steven's user avatar
  • 29.5k
11 votes
Accepted

Why are $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ compatible?

However, if P != NP then both NP and coNP are in exptime and not better. This is not neccesarily true. It just means that some NP (and coNP) problems cannot be solved in polynomial time. This is not ...
Tom van der Zanden's user avatar
10 votes

Why are Chess, Mario, and Go not NP-complete?

Your understanding of what makes chess NP-Hard is slightly flawed. Yes, a nondeterministic machine is able to "play perfectly". But the language of chess is, $$Chess = \{Pos \quad | \quad \text{White ...
Lieuwe Vinkhuijzen's user avatar
10 votes

There are pretty much no algorithms in P

The premise of your question is mistaken. The complexity is expressed as a function of the length $n$ of the input. "Does the input contain a specific, fixed bit pattern" (e.g., does it contain ...
David Richerby's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible