ContactPerson: aduri@cse.buffalo.edu
### Begin Citation ### Do not delete this line ###
%R 2001-02
%U /u0/csgrad/aduri/tmp/file.ps
%A Pavan, A.
%A Selman, A.L.
%T Separation of NP-completeness Notions
%D January 16, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%X We use hypotheses of structural 
    complexity theory to separate various NP-completeness notions. 
    In particular, we introduce an hypothesis from which 
    we describe a set in NP that is $\T$-complete but not 
    $\tt$-complete.  We provide fairly thorough analyses of the hypotheses that 
    we introduce.