<p>Here is an example, which appears a natural problem.</p>

<p><strong>Instance:</strong> Positive integers, $d_1,\ldots,d_n$ and $k$, all bounded from above by $n$.</p>

<p><strong>Question:</strong> Does there exist a $k$-colorable graph with degree sequence  $d_1,\ldots,d_n$ ?</p>

<p>Here the input can be described with $O(n\log n)$ bits, but the witness may require $\Omega(n^2)$ bits. </p>

<p><em>Remark:</em> I do not have a reference that this particular problem is indeed NP-complete. But the requirement of $k$-colorability could be replaced by any other NP-complete condition; the problem will likely become NP-complete for some condition, if not for this one.</p>

CC BY-SA 3.0
2015-10-07T05:57:45.853Z
To me, this problem has the wrong kind of structure to be NP-complete, unless P=NP.  The classes of graphs defined by each degree sequence can be very large, and many of them may have $n$-colourable elements for a trivial reason.
András Salamon
CC BY-SA 3.0
2015-10-07T16:18:53.323Z
@AndrásSalamon Indeed, I do not know what the complexity of this problem is, or whether it can be made NP-complete by choosing an appropriate condition instead of $k$-colorability. On the other hand, I would be surprised if for **every** polytime checkable property $Q$ the following problem would be in **P**: does there exist a graph with  a given degree sequence, such that it also has property $Q$?
Andras Farago
CC BY-SA 3.0
2015-10-07T23:04:03.863Z
I agree that it seems unlikely that degree sequence + property is always in P, but perhaps some of these are candidates for NP-intermediate status?
András Salamon
CC BY-SA 3.0
2015-10-09T14:59:38.050Z
@AndrásSalamon Yes, I can very well imagine that some of them has NPI status.
Andras Farago
CC BY-SA 3.0
2014-11-21T17:13:09.320Z
2014-11-21T17:13:09.320Z
Andras Farago
<p>I came along some quite natural NP-complete problems that seemingly require long witnesses. The problems, parameterized by integers $C$ and $D$ are as follows:</p>

<p><strong>Input:</strong> A one-tape TM $M$<br/>
<strong>Question:</strong> Is there some $n\in\mathbb{N}$, such that $M$ makes more than $Cn+D$ steps on some input of length $n$?</p>

<p>Sometimes the complement of the problem is easier to state: <em>Does a given one-tape TM $M$ run in time $Cn+D$, ie. does it make at most $Cn+D$ steps on all inputs of size $n$, for all $n$?</em></p>

<p>The full result is presented <a href="http://arxiv.org/abs/1312.0496">here</a>. Basically, it is shown that if we want to verify whether a one-tape TM runs in time $Cn+D$, we only need to verify this on inputs of length bounded by $q^{O(C)}$, where $q$ is the number of states of the input TM. So the witness would be the input of length $q^{O(C)}$ for which the time bound is violated. It is also shown in the reference that these problems are NP-complete for all $C\geq 2$ and $D\geq 1$.</p>

<p>Now if the witness is an input that violates the running time, it has to be of length $q^{\Omega(C)}$ in general. And the input is of length $O(q^2)$.</p>

CC BY-SA 3.0
2014-10-29T07:47:48.003Z
Thanks! But, to be honest, I find more "natural" (I know it's not a formal concept) the problem: "Given a formula $\varphi$, decide if it has at least $|\varphi|^2$ satisfying assignments" :-)
Marzio De Biasi
CC BY-SA 3.0
2014-10-29T17:18:22.360Z
I understand :). On the other hand, the problem about $\varphi$ has the length of the witness in the question, while the problem about TMs gets the length of the witness in the proof. What is more, the length of the witness is not _intentionally_ incorporated into the problem.
David G
CC BY-SA 3.0
2014-10-29T02:08:46.863Z
2014-10-29T05:08:30.700Z
2014-10-29T05:08:30.700Z
David G
<p>How about the edge coloring number in a dense graph (aka <a href="http://en.wikipedia.org/wiki/Edge_coloring" rel="nofollow noreferrer">Chromatic index</a>)? You are given the adjacency matrix of an $n$ vertex graph ($n^2$ bit input), but the <em>natural</em> witness describing the coloring has size $n^2\log n$. Of course, there might be shorter proofs for class 1 graphs in <a href="http://en.wikipedia.org/wiki/Vizing&#39;s_theorem" rel="nofollow noreferrer">Vizing's theorem</a>.</p>

<p>See also this <a href="https://cstheory.stackexchange.com/questions/16148/problem-unsolvable-in-2on-on-inputs-with-n-bits-assuming-eth?rq=1">possibly related question</a> </p>

CC BY-SA 3.0
2014-10-28T08:01:03.187Z
It seems a good example! Just a note: the problem is NP-complete even for cubic graphs; in that case we have that a witness of size $2|E|$ bits is enough (two bits for every edge) which is less than $n^2$ if we use the adjacency matrix representation and I suspect that it is less than the instance size whatever reasonable encoding we use for the cubic graph.
Marzio De Biasi
CC BY-SA 3.0
2014-10-28T06:49:06.790Z
2014-10-28T06:49:06.790Z
2017-04-13T12:32:28.080Z
Andreas Björklund
<p>Maybe this is a silly "reason/explanation", but for many NP-Complete problems, a solution is a subset of the input (knapsack, vertex cover, clique, dominating set, independent set, max cut, subset sum, ...) or a permutation of or assignment to a subset of the input (Hamiltonian path, traveling salesman, SAT, graph isomorphism, graph coloring, ...).</p>

<p>We could try to read more into it than that, or come up with a more fancily-stated reason, but I'm not sure whether there is anything deeper going on or not.</p>

CC BY-SA 3.0
2014-10-27T07:42:42.050Z
I think this is a fine "first idea" indeed. Sometimes the problems can't be classified unambiguously. For instance, SAT could also be a subset problem ("choose a subset of true variables"). Or is HAMCYCLE a permutation problem on vertices, or a subset problem on edges? (BTW, maybe the "assignment problems" could really be "partition problems", think of say 3-coloring).
Juho
CC BY-SA 3.0
2014-10-27T02:52:22.597Z
2014-10-27T02:52:22.597Z
usul
<p>As for your first question, Allender states (in <a href="http://iuuk.mff.cuni.cz/~koucky/papers/gap.pdf" rel="nofollow">Amplifying Lower Bounds by Means of Self-Reducibility</a>) that no natural NP-complete problem is known to lie outside of NTIME(n). This means that all known natural NP-complete sets have linear size witnesses.</p>

CC BY-SA 3.0
2015-10-02T21:22:06.357Z
Note that the length of the longest accepting path in nondeterministic Turing machine corresponds to the size of the witness.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-10-02T19:50:05.693Z
2015-10-02T19:50:05.693Z
Mohammad Al-Turkistany
<p>Consider the following variant of the <em>MAXCLIQUE</em> problem.</p>

<p><strong>Instance:</strong> A circuit $C$ with $2n$ input bits, and of polynomially bounded size in $n$. This circuit implicitly determines a graph on $2^n$ vertices, such that each vertex is identified with an $n$-bit string, and two vertices are connected with an edge if the $2n$-bit string that is obtained by concatenating the two vertex IDs, is accepted by $C$. Let $G(C)$ denote this graph. Note that it has exponentially many vertices in $n$, but is still determined by the polynomial size description of $C$.</p>

<p><strong>Question:</strong> Does $G(C)$ contain a clique of size $n^k$, where $k$ is a fixed  constant?</p>

<p><strong>Notes:</strong></p>

<ol>
<li><p>The problem is NP-complete. The containment in $NP$ is obvious. Completeness can be proved by observing that if the circuit accepts only vertex pairs in which each ID is at most $N=2n^k$, then $G(C)$ can be  an arbitrary $N$-vertex graph plus many isolated vertices. (Any such $N$-vertex graph can be encoded in $C$, since $C$ is allowed to have polynomial size in $n$, and so also in $N$.) Then the question becomes: is there an $N/2$-sized clique in an $N$-vertex graph? This is known to be NP-complete, for general $N$. The issue that $N$ is not arbitrary, it is restricted to $N=2n^k$, can be eliminated by appropriate padding. </p></li>
<li><p>The natural witness for the original problem is the $n^k$-sized clique, which can be described by an $O(n^{k+1})$ long string (an $n$-bit string for each of the $n^k$ vertices).  Note that $k$ can  be a very large constant, so the witness can be much longer than linear. (Even if the input size is the description of $C$, rather than $n$, this witness can be still much longer, because $k$ can be chosen independently of $C$.) </p></li>
<li><p>The problem can be viewed as natural, since it is a variant of <em>MAXCLIQUE</em>. </p></li>
<li><p>When Allender wrote "no natural NP-complete problem is known to lie outside of $NTIME(n)$," (see <a href="http://iuuk.mff.cuni.cz/~koucky/papers/gap.pdf" rel="nofollow">Amplifying Lower Bounds by Means of Self-Reducibility</a>, Section 7), he may have had a narrower concept of naturalness in mind. For example, natural could be narrowed to something that people <em>really</em> want to solve on the grounds of independent, practical motivations. It is not enough if the problem is not constructed via diagonalization. </p></li>
</ol>

CC BY-SA 3.0
2015-10-05T11:17:22.987Z
I am not sure I follow your reduction of Half-Clique to this problem, to establish completeness in NP.  Given an $n$-vertex instance of Half-Clique, what circuit does it map to?
András Salamon
CC BY-SA 3.0
2015-10-05T15:21:19.617Z
@AndrásSalamon Let $G'$ be an $N=2n^k$-vertex graph, serving as input graph of Half-Clique. Then $C$ is the circuit that accepts any node pair $(u,v)$, if $u\leq N, \; v\leq N$ (as binary numbers), and $(u,v)\in E(G')$, otherwise $C$ rejects. (This $C$ can be implemented as a polynomial sized circuit.) Then $G(C)$ will contain $G'$ on the first $N$ nodes, plus $2^n-N$ additional isolated nodes. The graph $G(C)$ has a clique of size $n^k$ precisely when $G'$ has a half-clique.
Andras Farago
CC BY-SA 3.0
2015-10-04T23:51:55.763Z
2015-10-05T01:39:28.557Z
2015-10-05T01:39:28.557Z
Andras Farago
<p>The question on cstheory "<a href="https://cstheory.stackexchange.com/q/11422/3247">What is NP restricted to linear size witnesses?</a>" asks about the class NP restricted to linear size $O(n)$ witnesses, but</p>

<blockquote>
  <p>Are there <em>natural</em> NP-complete problems in which (yes) instances
  of size $n$ require witnesses of size greater than $n$?</p>
</blockquote>

<p>Clearly we can build <em>artificial</em> problems like:</p>

<ul>
<li>$L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$</li>
<li>$L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$</li>
</ul>

<p>After a quick look at G&amp;J, every natural NPC problem seems to have witnesses (strictly) smaller than $n$.</p>

<blockquote>
  <p>Is there a "reason/explanation" for it ?</p>
</blockquote>

CC BY-SA 3.0
2014-10-26T20:32:54.313Z
Many problems have witness size $\Theta(n \log n)$, like graph isomorphism and Hamiltonian path. Did you want to exclude polylog factors, or does that count as an answer?
Joshua Grochow
CC BY-SA 3.0
2014-10-26T20:54:21.073Z
Actually, the witness size for Graph Isomorphism and Hamiltonian Path could be seen as *sublinear* in the input (given that the input is the $n \times n$ adjacency matrix of the graph).
Ryan Williams
CC BY-SA 3.0
2014-10-26T22:57:51.050Z
@JoshuaGrochow: a witness for the HP and GI problems is a permutation of the nodes, which should (?) take fewer bits (under a reasonable encoding) than the full description of the graph(s).
Marzio De Biasi
CC BY-SA 3.0
2014-10-26T23:03:46.467Z
These are decision version of substructure search problems, you may want to look for problems which cannot be expressed in monadic existential second order logic.
Kaveh
CC BY-SA 3.0
2014-10-27T03:26:18.490Z
Oh, right...d'oh.
Joshua Grochow
CC BY-SA 3.0
2014-10-29T23:14:24.513Z
@MarzioDeBiasi I think your observation of small witnesses should be used to define **natural** NP-complete problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-10-30T09:41:48.103Z
@MarzioDeBiasi - How do you prove that the second language you offered ($\phi^2$ assignments) have no $O(n)$-sized witnesses?
R B
CC BY-SA 3.0
2014-10-30T10:55:14.307Z
@RB: by definition: a (valid) witness of the problem is the (polynomial-size) list of the $|\varphi|^2$ satisfying assignments for $\varphi$ (if they exist). BTW the reduction (from SAT) to prove that (2) is NPC is not so immediate: adding a clause or a variable means increasing the size of $\varphi$, so one must play a little bit with dum or repeated variables/clauses.
Marzio De Biasi
CC BY-SA 3.0
2014-10-30T10:58:10.250Z
@MarzioDeBiasi - I agree that a list of the satisfying assignments is enough, but can you *prove* that there is no shorter witness for the problem? (maybe a succinct way of representing the needed assignments).
R B
CC BY-SA 3.0
2014-10-30T11:08:33.017Z
@MarzioDeBiasi - The language, as defined in the question is merely the set of all such SAT formulas. If you *define* the witness size then this is no longer interesting (you can always take a problem, say HAMILTONICITY, and define the witness to be super-polynomial in length without any reason).
R B
CC BY-SA 3.0
2014-10-30T11:24:21.170Z
@RB: mmm ... perhaps you're right; let me think about it.
Marzio De Biasi
CC BY-SA 3.0
2014-11-05T18:43:23.260Z
Suppose a problem in NP requires certificates of size $s(n)$, for some well-behaved function $s(n) \in \omega(n \log n)$.  As these are the shortest possible certificates, the problem must also require at least $s(n)$ nondeterministic time steps, just to visit the entire input; otherwise the certificate could be shortened to just the reachable part of the tape.

Any lower bound on $s(n)$ will therefore also be a lower bound on the time complexity of the problem.

Hence you are asking for even more than a problem in NP that is not in $NTIME(n^k)$ for some $k > 1$, and already quite challenging.
András Salamon
<cc.complexity-theory><np><proof-complexity>
Natural NP-complete problems with "large" witnesses
Marzio De Biasi
# Natural NP-complete problems with "large" witnesses

(Asked by: username_0 on 2014-10-26)

The question on cstheory "[What is NP restricted to linear size witnesses?](https://cstheory.stackexchange.com/q/11422/3247)" asks about the class NP restricted to linear size $O(n)$ witnesses, but

> Are there *natural* NP-complete problems in which (yes) instances
> of size $n$ require witnesses of size greater than $n$?

Clearly we can build *artificial* problems like:

* $L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$
* $L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

After a quick look at G&J, every natural NPC problem seems to have witnesses (strictly) smaller than $n$.

> Is there a "reason/explanation" for it ?

**Tags:** cc.complexity-theory, np, proof-complexity

> **Comments:**
> **username_1**: Many problems have witness size $\Theta(n \log n)$, like graph isomorphism and Hamiltonian path. Did you want to exclude polylog factors, or does that count as an answer?  
> **username_2**: Actually, the witness size for Graph Isomorphism and Hamiltonian Path could be seen as *sublinear* in the input (given that the input is the $n \times n$ adjacency matrix of the graph).  
> **username_0**: @JoshuaGrochow: a witness for the HP and GI problems is a permutation of the nodes, which should (?) take fewer bits (under a reasonable encoding) than the full description of the graph(s).  
> **username_3**: These are decision version of substructure search problems, you may want to look for problems which cannot be expressed in monadic existential second order logic.  
> **username_1**: Oh, right...d'oh.  
> **username_4**: @MarzioDeBiasi I think your observation of small witnesses should be used to define **natural** NP-complete problem.  
> **username_5**: @MarzioDeBiasi - How do you prove that the second language you offered ($\phi^2$ assignments) have no $O(n)$-sized witnesses?  
> **username_0**: @RB: by definition: a (valid) witness of the problem is the (polynomial-size) list of the $|\varphi|^2$ satisfying assignments for $\varphi$ (if they exist). BTW the reduction (from SAT) to prove that (2) is NPC is not so immediate: adding a clause or a variable means increasing the size of $\varphi$, so one must play a little bit with dum or repeated variables/clauses.  
> **username_5**: @MarzioDeBiasi - I agree that a list of the satisfying assignments is enough, but can you *prove* that there is no shorter witness for the problem? (maybe a succinct way of representing the needed assignments).  
> **username_5**: @MarzioDeBiasi - The language, as defined in the question is merely the set of all such SAT formulas. If you *define* the witness size then this is no longer interesting (you can always take a problem, say HAMILTONICITY, and define the witness to be super-polynomial in length without any reason).  
> **username_0**: @RB: mmm ... perhaps you're right; let me think about it.  
> **username_6**: Suppose a problem in NP requires certificates of size $s(n)$, for some well-behaved function $s(n) \in \omega(n \log n)$.  As these are the shortest possible certificates, the problem must also require at least $s(n)$ nondeterministic time steps, just to visit the entire input; otherwise the certificate could be shortened to just the reachable part of the tape.  Any lower bound on $s(n)$ will therefore also be a lower bound on the time complexity of the problem.  Hence you are asking for even more than a problem in NP that is not in $NTIME(n^k)$ for some $k > 1$, and already quite challenging.  

---

## 6 answers

### Answer by username_9 on 2014-10-28. Score: 10

How about the edge coloring number in a dense graph (aka [Chromatic index](http://en.wikipedia.org/wiki/Edge_coloring))? You are given the adjacency matrix of an $n$ vertex graph ($n^2$ bit input), but the *natural* witness describing the coloring has size $n^2\log n$. Of course, there might be shorter proofs for class 1 graphs in [Vizing's theorem](http://en.wikipedia.org/wiki/Vizing's_theorem).

See also this [possibly related question](https://cstheory.stackexchange.com/questions/16148/problem-unsolvable-in-2on-on-inputs-with-n-bits-assuming-eth?rq=1)

> **Comments:**
> **username_0**: It seems a good example! Just a note: the problem is NP-complete even for cubic graphs; in that case we have that a witness of size $2|E|$ bits is enough (two bits for every edge) which is less than $n^2$ if we use the adjacency matrix representation and I suspect that it is less than the instance size whatever reasonable encoding we use for the cubic graph.  

---

### Answer by username_7 on 2014-11-21. Score: 8

Here is an example, which appears a natural problem.

**Instance:** Positive integers, $d\_1,\ldots,d\_n$ and $k$, all bounded from above by $n$.

**Question:** Does there exist a $k$-colorable graph with degree sequence $d\_1,\ldots,d\_n$ ?

Here the input can be described with $O(n\log n)$ bits, but the witness may require $\Omega(n^2)$ bits.

*Remark:* I do not have a reference that this particular problem is indeed NP-complete. But the requirement of $k$-colorability could be replaced by any other NP-complete condition; the problem will likely become NP-complete for some condition, if not for this one.

> **Comments:**
> **username_6**: To me, this problem has the wrong kind of structure to be NP-complete, unless P=NP.  The classes of graphs defined by each degree sequence can be very large, and many of them may have $n$-colourable elements for a trivial reason.  
> **username_7**: @AndrásSalamon Indeed, I do not know what the complexity of this problem is, or whether it can be made NP-complete by choosing an appropriate condition instead of $k$-colorability. On the other hand, I would be surprised if for **every** polytime checkable property $Q$ the following problem would be in **P**: does there exist a graph with  a given degree sequence, such that it also has property $Q$?  
> **username_6**: I agree that it seems unlikely that degree sequence + property is always in P, but perhaps some of these are candidates for NP-intermediate status?  
> **username_7**: @AndrásSalamon Yes, I can very well imagine that some of them has NPI status.  

---

### Answer by username_8 on 2014-10-29. Score: 8

I came along some quite natural NP-complete problems that seemingly require long witnesses. The problems, parameterized by integers $C$ and $D$ are as follows:

**Input:** A one-tape TM $M$  
**Question:** Is there some $n\in\mathbb{N}$, such that $M$ makes more than $Cn+D$ steps on some input of length $n$?

Sometimes the complement of the problem is easier to state: *Does a given one-tape TM $M$ run in time $Cn+D$, ie. does it make at most $Cn+D$ steps on all inputs of size $n$, for all $n$?*

The full result is presented [here](http://arxiv.org/abs/1312.0496). Basically, it is shown that if we want to verify whether a one-tape TM runs in time $Cn+D$, we only need to verify this on inputs of length bounded by $q^{O(C)}$, where $q$ is the number of states of the input TM. So the witness would be the input of length $q^{O(C)}$ for which the time bound is violated. It is also shown in the reference that these problems are NP-complete for all $C\geq 2$ and $D\geq 1$.

Now if the witness is an input that violates the running time, it has to be of length $q^{\Omega(C)}$ in general. And the input is of length $O(q^2)$.

> **Comments:**
> **username_0**: Thanks! But, to be honest, I find more "natural" (I know it's not a formal concept) the problem: "Given a formula $\varphi$, decide if it has at least $|\varphi|^2$ satisfying assignments" :-)  
> **username_8**: I understand :). On the other hand, the problem about $\varphi$ has the length of the witness in the question, while the problem about TMs gets the length of the witness in the proof. What is more, the length of the witness is not _intentionally_ incorporated into the problem.  

---

### Answer by username_10 on 2014-10-27. Score: 6

Maybe this is a silly "reason/explanation", but for many NP-Complete problems, a solution is a subset of the input (knapsack, vertex cover, clique, dominating set, independent set, max cut, subset sum, ...) or a permutation of or assignment to a subset of the input (Hamiltonian path, traveling salesman, SAT, graph isomorphism, graph coloring, ...).

We could try to read more into it than that, or come up with a more fancily-stated reason, but I'm not sure whether there is anything deeper going on or not.

> **Comments:**
> **username_11**: I think this is a fine "first idea" indeed. Sometimes the problems can't be classified unambiguously. For instance, SAT could also be a subset problem ("choose a subset of true variables"). Or is HAMCYCLE a permutation problem on vertices, or a subset problem on edges? (BTW, maybe the "assignment problems" could really be "partition problems", think of say 3-coloring).  

---

### Answer by username_4 on 2015-10-02. Score: 3

As for your first question, Allender states (in [Amplifying Lower Bounds by Means of Self-Reducibility](http://iuuk.mff.cuni.cz/~koucky/papers/gap.pdf)) that no natural NP-complete problem is known to lie outside of NTIME(n). This means that all known natural NP-complete sets have linear size witnesses.

> **Comments:**
> **username_4**: Note that the length of the longest accepting path in nondeterministic Turing machine corresponds to the size of the witness.  

---

### Answer by username_7 on 2015-10-04. Score: 1

Consider the following variant of the *MAXCLIQUE* problem.

**Instance:** A circuit $C$ with $2n$ input bits, and of polynomially bounded size in $n$. This circuit implicitly determines a graph on $2^n$ vertices, such that each vertex is identified with an $n$-bit string, and two vertices are connected with an edge if the $2n$-bit string that is obtained by concatenating the two vertex IDs, is accepted by $C$. Let $G(C)$ denote this graph. Note that it has exponentially many vertices in $n$, but is still determined by the polynomial size description of $C$.

**Question:** Does $G(C)$ contain a clique of size $n^k$, where $k$ is a fixed constant?

**Notes:**

1. The problem is NP-complete. The containment in $NP$ is obvious. Completeness can be proved by observing that if the circuit accepts only vertex pairs in which each ID is at most $N=2n^k$, then $G(C)$ can be an arbitrary $N$-vertex graph plus many isolated vertices. (Any such $N$-vertex graph can be encoded in $C$, since $C$ is allowed to have polynomial size in $n$, and so also in $N$.) Then the question becomes: is there an $N/2$-sized clique in an $N$-vertex graph? This is known to be NP-complete, for general $N$. The issue that $N$ is not arbitrary, it is restricted to $N=2n^k$, can be eliminated by appropriate padding.
2. The natural witness for the original problem is the $n^k$-sized clique, which can be described by an $O(n^{k+1})$ long string (an $n$-bit string for each of the $n^k$ vertices). Note that $k$ can be a very large constant, so the witness can be much longer than linear. (Even if the input size is the description of $C$, rather than $n$, this witness can be still much longer, because $k$ can be chosen independently of $C$.)
3. The problem can be viewed as natural, since it is a variant of *MAXCLIQUE*.
4. When Allender wrote "no natural NP-complete problem is known to lie outside of $NTIME(n)$," (see [Amplifying Lower Bounds by Means of Self-Reducibility](http://iuuk.mff.cuni.cz/~koucky/papers/gap.pdf), Section 7), he may have had a narrower concept of naturalness in mind. For example, natural could be narrowed to something that people *really* want to solve on the grounds of independent, practical motivations. It is not enough if the problem is not constructed via diagonalization.

> **Comments:**
> **username_6**: I am not sure I follow your reduction of Half-Clique to this problem, to establish completeness in NP.  Given an $n$-vertex instance of Half-Clique, what circuit does it map to?  
> **username_7**: @AndrásSalamon Let $G'$ be an $N=2n^k$-vertex graph, serving as input graph of Half-Clique. Then $C$ is the circuit that accepts any node pair $(u,v)$, if $u\leq N, \; v\leq N$ (as binary numbers), and $(u,v)\in E(G')$, otherwise $C$ rejects. (This $C$ can be implemented as a polynomial sized circuit.) Then $G(C)$ will contain $G'$ on the first $N$ nodes, plus $2^n-N$ additional isolated nodes. The graph $G(C)$ has a clique of size $n^k$ precisely when $G'$ has a half-clique.  

---

