Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR06-062 | 29th June 2006 00:00

#### Unique k-SAT is as Hard as k-SAT

Revision #1
Authors: Subhas Kumar Ghosh
Accepted on: 29th June 2006 00:00
Keywords:

Abstract:

In this work we show that Unique k-SAT is as hard as k-SAT for every $k \in {\mathds N}$.

### Paper:

TR06-062 | 24th April 2006 00:00

#### Unique k-SAT is as Hard as k-SAT

TR06-062
Authors: Subhas Kumar Ghosh
Publication: 7th May 2006 21:01
Keywords:

Abstract:

In this work we show that Unique k-SAT is as Hard as k-SAT for every $k \in {\mathds N}$. This settles a conjecture by Calabro, Impagliazzo, Kabanets and Paturi \cite{CIKP03}. To provide an affirmative answer to this conjecture, we develop a randomness optimal construction of Isolation Lemma(see Valiant and Vazirani \cite{VV85}) for $k$-\sat, using $\Omega\left(\log{s}\right)$ number of random bits, to isolate an element of a family of size ${\cal O}\left(2^s\right)$. It shown by Chari, Rohatgi and Srinivasan in \cite{CRS93}, that $\Omega\left(\log{s}\right)$ number of random bits is the lower-bound of randomness complexity for Isolation Lemma.

### Comment(s):

Comment #1 to TR06-062 | 29th July 2006 13:42

#### Comments on "Unique k-SAT is as Hard as k-SAT" Comment on: TR06-062

Comment #1
Authors: Chris Calabro
Accepted on: 29th July 2006 13:42
Keywords:

Abstract:

The paper "Unique $k$-SAT is as Hard as $k$-SAT",
by Subhas Kumar Ghosh, has many flaws,
both technical and academic, and
some invalidate the proof of the main result.
The following comments describe some of the errors.
It is assumed that the reader is intimately familiar
with the paper.

Comment #2 to TR06-062 | 29th July 2006 13:42

#### Some things I could not understand in TR06-062 Comment on: TR06-062

Comment #2
Authors: Yann Barsamian
Accepted on: 29th July 2006 13:42
Keywords:

Abstract:

After reading the whole paper, I did not understood
some parts of the proofs used in it.

Comment #3 to TR06-062 | 29th July 2006 13:44

#### Comment on first submission

Comment #3
Authors: Subhas Kumar Ghosh
Accepted on: 29th July 2006 13:44