On Isomorphisms and Density of $NP$ and Other Complete Sets
From MaRDI portal
Publication:4128010
DOI10.1137/0206023zbMath0356.68059OpenAlexW2090186532WikidataQ55918643 ScholiaQ55918643MaRDI QIDQ4128010
No author found.
Publication date: 1977
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/7101
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)
Related Items
Reductions among polynomial isomorphism types, Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, One-way functions and the isomorphism conjecture, The random oracle hypothesis is false, Complexity and dimension, Space-efficient recognition of sparse self-reducible languages, Continuous optimization problems and a polynomial hierarchy of real functions, Sparse sets, approximable sets, and parallel queries to NP, Generalized juntas and NP-hard sets, Locating \(P\)/poly optimally in the extended low hierarchy, NP is as easy as detecting unique solutions, On solving hard problems by polynomial-size circuits, Computation times of NP sets of different densities, Almost every set in exponential time is P-bi-immune, A comparison of polynomial time completeness notions, On hardness of one-way functions, On one-way functions and polynomial-time isomorphisms, On helping by robust oracle machines, Scalability and the isomorphism problem, A classification of complexity core lattices, On simple and creative sets in NP, Can the catenation of two weakly sparse languages be dense?, The complexity of optimization problems, Isomorphisms and 1-L reductions, DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization, An excursion to the Kolmogorov random strings, The isomorphism conjecture holds and one-way functions exist relative to an oracle, On P-immunity of exponential time complete sets, Complexity classes without machines: on complete languages for UP, Collapsing degrees, Index sets and presentations of complexity classes, Complexity results in graph reconstruction, Graph isomorphism is in the low hierarchy, Notes on polynomial levelability, Comparing reductions to NP-complete sets, No NP problems averaging over ranking of distributions are harder, On vanishing of Kronecker coefficients, The isomorphism conjecture for constant depth reductions, An oracle builder's toolkit, Discrete extremal problems, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], Honest polynomial time reducibilities and the \(P=?NP\) problem, New developments in structural complexity theory, On the structure of sets in NP and other complexity classes, Kolmogorov complexity and degrees of tally sets, A note on natural complete sets and Goedel numberings, A note on sparse oracles for NP, Bi-immunity results for cheatable sets, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, Inverting onto functions., Separating NE from some nonuniform nondeterministic complexity classes, On sparse sets in NP-P, An appraisal of computational complexity for operations researchers, On sets polynomially enumerable by iteration, On p-creative sets and p-completely creative sets, Nonuniform complexity and the randomness of certain complete languages, Cook versus Karp-Levin: Separating completeness notions if NP is not small, On quasilinear-time complexity theory, A note on P-selective sets and closeness, Oracles for structural properties: The isomorphism problem and public-key cryptography, Logarithmic advice classes, Universal relations and {\#}P-completeness, The complexity of unions of disjoint sets, Local restrictions from the Furst-Saxe-Sipser paper, Polynomial-time compression, Relativized isomorphisms of NP-complete sets, Sparse selfreducible sets and nonuniform lower bounds, Collapsing and separating completeness notions under average-case and worst-case hypotheses, Circuit size relative to pseudorandom oracles, On sparse hard sets for counting classes, The fault tolerance of NP-hard problems, On sparseness, reducibilities, and complexity, Core instances for testing: a case study, The strong exponential hierarchy collapses, On polynomial time isomorphisms of some new complete sets, On log-tape isomorphisms of complete sets, Exponential-time and subexponential-time sets, Probabilistic complexity classes and lowness, The effective entropies of some extensions of context-free languages, Non-mitotic sets, Effective entropies and data compression, On the p-isomorphism conjecture, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets, Some consequences of the existnce of pseudorandom generators, Sparse hard sets for P: Resolution of a conjecture of Hartmanis, Resolution of Hartmanis' conjecture for NL-hard sparse sets, On hard instances, A low and a high hierarchy within NP, On self-reducibility and weak P-selectivity, Some consequences of non-uniform conditions on uniform classes, Polynomial time computations in models of ET, On small generators, The relative power of logspace and polynomial time reductions, Robust algorithms: a different approach to oracles, On some natural complete operators, Quasi-injective reductions, Padding, commitment and self-reducibility, On one-one polynomial time equivalence relations, Independence results about context-free languages and lower bounds, Uniformly hard languages., One-way permutations and self-witnessing languages, A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly, Collapsing degrees via strong computation, Nonlevelable sets and immune sets in the accepting density hierarchy inNP, Computational complexity of synchronization under sparse regular constraints, Completeness for nondeterministic complexity classes, Structural complexity theory: Recent surprises, Unnamed Item, Query-monotonic Turing reductions, Separating the low and high hierarchies by oracles, One-way functions and the nonisomorphism of NP-complete sets, On uniformity within \(NC^ 1\), Polynomial time quantum computation with advice, Nonuniform reductions and NP-completeness, Separating NE from Some Nonuniform Nondeterministic Complexity Classes, On the complexity of graph reconstruction, A survey of one-way functions in complexity theory, A new algorithm design technique for hard problems, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Complete problems and strong polynomial reducibilities, The degree structure of 1-L reductions, Characterizing regular languages with polynomial densities, Rankable distributions do not provide harder instances than uniform distributions, Polynomial-time axioms of choice and polynomial-time cardinality, Productive functions and isomorphisms, On the equivalence of two post-quantum cryptographic families, Classifying the computational complexity of problems, OnP-subset structures, Non-uniform reductions, ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES, The complexity of counting edge colorings for simple graphs, ON UNIVERSALLY POLYNOMIAL CONTEXT-FREE LANGUAGES, On sparseness and Turing reducibility over the reals, On the power of parity polynomial time, Strong Reductions and Isomorphism of Complete Sets, Reductions to sets of low information content, The Fault Tolerance of NP-Hard Problems, Hard Instances of Algorithms and Proof Systems, Non-mitotic Sets, Unions of Disjoint NP-Complete Sets, On the computational complexity of the Jones and Tutte polynomials, Investigations Concerning the Structure of Complete Sets, Monotonous and randomized reductions to sparse sets, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS, Relativizing relativized computations, Almost every set in exponential time is P-bi-immune, On inefficient special cases of NP-complete problems, Distinguishing conjunctive and disjunctive reducibilities by sparse sets, Complete sets and closeness to complexity classes, Linear time transformations between combinatorial problems, All superlinear inverse schemes are coNP-hard, Resource bounded immunity and simplicity, What can be efficiently reduced to the Kolmogorov-random strings?, Tally NP sets and easy census functions., Bi-immune sets for complexity classes