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 (only showing first 100 items - show all)
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 ⋮ 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
This page was built for publication: On Isomorphisms and Density of $NP$ and Other Complete Sets
