Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Samik Sengupta:

TR04-019 | 15th January 2004
Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta

Properties of NP-Complete Sets

We study several properties of sets that are complete for NP.
We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$
such ... more >>>

TR04-007 | 13th January 2004
Alan L. Selman, Samik Sengupta

Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy

Revisions: 1 , Comments: 1

It is known \cite{BHZ87} that if every language in coNP has a
constant-round interactive proof system, then the polynomial hierarchy
collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that
#SAT, the #P-complete function that outputs the number of satisfying
assignments of a Boolean ... more >>>

TR03-027 | 21st April 2003
Christian Glaßer, Alan L. Selman, Samik Sengupta

Reductions between Disjoint NP-Pairs

We prove that all of the following assertions are equivalent:
There is a many-one complete disjoint NP-pair;
there is a strongly many-one complete disjoint NP-pair;
there is a Turing complete disjoint NP-pair such that all reductions
are smart reductions;
there is a complete disjoint NP-pair for one-to-one, invertible ... more >>>

TR03-011 | 17th February 2003
Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

Disjoint NP-Pairs

We study the question of whether the class DisNP of
disjoint pairs (A, B) of NP-sets contains a complete pair.
The question relates to the question of whether optimal
proof systems exist, and we relate it to the previously
studied question of whether there exists ... more >>>

ISSN 1433-8092 | Imprint