1
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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 nO(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 nO(log n).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.