On some natural complete operators

DOI10.1016/0304-3975(85)90085-4zbMath0576.68033OpenAlexW2070323038MaRDI QIDQ1064780

Ker-I. Ko

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90085-4

zbMATH Keywords

completenessNPComplexity classes of operatorsoracle Turing machinesreducibilities on operators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

One-way permutations and self-witnessing languages, Continuous optimization problems and a polynomial hierarchy of real functions, A note on quadratic residuosity and UP, Nondeterministic functions and the existence of optimal proof systems, Honest polynomial degrees and \(P=?NP\), On hardness of one-way functions, On one-way functions and polynomial-time isomorphisms, Some observations on the connection between counting and recursion, Every polynomial-time 1-degree collapses if and only if P = PSPACE, A tight relationship between generic oracles and type-2 complexity theory, On intractability of the classUP, Tight lower bounds on the ambiguity of strong, total, associative, one-way functions, A survey of one-way functions in complexity theory, Promise problems and access to unambiguous computation, Polynomial-time axioms of choice and polynomial-time cardinality, On continuous one-way functions, Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions, In Memoriam: Ker-I Ko (1950–2018), Oracles for structural properties: The isomorphism problem and public-key cryptography, On polynomial time one-truth-table reducibility to a sparse set, Complexity of Operators on Compact Sets, The robustness of LWPP and WPP, with an application to graph reconstruction, If P \(\neq\) NP then some strongly noninvertible functions are invertible, Unnamed Item, Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Some consequences of non-uniform conditions on uniform classes
• Oracle-dependent properties of the lattice of NP sets
• On small generators
• A low and a high hierarchy within NP
• The computational complexity of maximization and integration
• On counting problems and the polynomial-time hierarchy
• Relative complexity of checking and evaluating
• Riemann's hypothesis and tests for primality
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Relationships between nondeterministic and deterministic tape complexities
• Relativized polynomial hierarchies extending two levels
• Immunity, Relativizations, and Nondeterminism
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Quantitative Relativizations of Complexity Classes
• The Complexity of Enumeration and Reliability Problems
• Polynomial Space and Transitive Closure
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativized Questions Involving Probabilistic Algorithms
• A note on complete sets and transitive closure
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• “Helping”: several formalizations
• Relativization of the Theory of Computational Complexity
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Indexing of subrecursive classes
• The complexity of theorem-proving procedures