<p>This is not a reference, but an NP-complete problem cannot have a polynomial-time self-reduction which halves the input size unless NP has a <i>n</i><sup>O(log <i>n</i>)</sup>-time algorithm, even if we allow Turing reductions.</p>

<p>Suppose there is a <i>p</i>(<i>n</i>)-time Turing reduction from an NP-complete problem <i>L</i> to itself such that given an input of length <i>n</i>, the reduction only makes queries to strings of length at most <i>n</i>/2.  Then you can convert this reduction to a standalone deterministic algorithm for <i>L</i> by using recursion.  By writing down a recurrence relation for the running time of this deterministic algorithm, it is not hard to see that it runs in time <i>n</i><sup>O(log <i>n</i>)</sup>.</p>

CC BY-SA 2.5
2011-04-02T15:39:54.030Z
2011-04-02T15:39:54.030Z
Tsuyoshi Ito
<p>I'm interested in the complexity of self reducibility of a variant clique problem. Namely, the NP-complete problem HALF Clique: given a graph on $N$ nodes, Is there a clique of size $N/2$ in the graph?</p>

<p>How hard is it to reduce an instance of HALF CLIQUE of input size $2N$ to an instance of size $N$ using Turing reduction? Is there a Cook reduction? I'm looking for references for upper bounds and lower bounds on the complexity of Turing reductions of this type.</p>

<cc.complexity-theory><reductions>
Complexity of Turing self-reducibility of Clique problem?
Mohammad Al-Turkistany
# Complexity of Turing self-reducibility of Clique problem?

(Asked by: username_0 on 2011-04-02)

I'm interested in the complexity of self reducibility of a variant clique problem. Namely, the NP-complete problem HALF Clique: given a graph on $N$ nodes, Is there a clique of size $N/2$ in the graph?

How hard is it to reduce an instance of HALF CLIQUE of input size $2N$ to an instance of size $N$ using Turing reduction? Is there a Cook reduction? I'm looking for references for upper bounds and lower bounds on the complexity of Turing reductions of this type.

**Tags:** cc.complexity-theory, reductions


---

## 1 answers

### Answer by username_1 on 2011-04-02. Score: 13 | Accepted answer

This is not a reference, but an NP-complete problem cannot have a polynomial-time self-reduction which halves the input size unless NP has a *n*O(log *n*)-time algorithm, even if we allow Turing reductions.

Suppose there is a *p*(*n*)-time Turing reduction from an NP-complete problem *L* to itself such that given an input of length *n*, the reduction only makes queries to strings of length at most *n*/2. Then you can convert this reduction to a standalone deterministic algorithm for *L* by using recursion. By writing down a recurrence relation for the running time of this deterministic algorithm, it is not hard to see that it runs in time *n*O(log *n*).


---

