Journal of Computer and System Sciences（JCSS ）的VOLUME 53, ISSUE 2论文列表

卷期号： Volume 53, Issue 2

发布时间： October 1996

卷期年份： 1996

EDITOR'S FOREWORD

Polynomial-Time Isomorphism of 1-L-Complete Sets

On Limited Nondeterminism and the Complexity of the V-C Dimension

On Closure Properties of #P in the Context of PF∘#P

Taking It to the Limit: On Infinite Variants of NP-Complete Problems

P-Selective Sets and Reducing Search to Decision vs Self-Reducibility

P-Selective Self-Reducible Sets: A New Characterization of P

Pointers versus Arithmetic in PRAMs

EDITOR'S FOREWORD: Special Issue on the 9th Annual Structure in Complexity Theory Conference in Amsterdam, June 28–July 1, 1994

Relative to a Random Oracle, NP Is Not Small

Multi-prover Encoding Schemes and Three-prover Proof Systems

Random Strings Make Hard Instances

On the Isomorphism Conjecture for Weak Reducibilities

Logical Definability of Counting Functions

On the Query Complexity of Clique Size and Maximum Satisfiability