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

__
TR04-007
| 13th January 2004
__

Alan L. Selman, Samik Sengupta#### Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy

Revisions: 1
,
Comments: 1

__
TR03-027
| 21st April 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta#### Reductions between Disjoint NP-Pairs

__
TR03-011
| 17th February 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang#### Disjoint NP-Pairs

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta

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 >>>

Alan L. Selman, Samik Sengupta

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 >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta

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 >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

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 >>>