The complexity of promise problems with applications to public-key cryptography
From MaRDI portal
Publication:3722415
DOI10.1016/S0019-9958(84)80056-XzbMath0592.94012WikidataQ29543805 ScholiaQ29543805MaRDI QIDQ3722415
Selman, Alan L., Yacov Yacobi, Shimon Even
Publication date: 1984
Published in: Information and Control (Search for Journal in Brave)
Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
A taxonomy of complexity classes of functions, On Black-Box Extensions of Non-interactive Zero-Knowledge Arguments, and Signatures Directly from Simulation Soundness, Resource-bounded kolmogorov complexity revisited, A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes, NP is as easy as detecting unique solutions, The Journey from NP to TFNP Hardness, Reductions between disjoint NP-pairs, Promise problems complete for complexity classes, A thirty year old conjecture about promise problems, Mathematical problems in cryptology, Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Unambiguous computations and locally definable acceptance types, Promise problems and access to unambiguous computation, Two Comments on Targeted Canonical Derandomizers, Public Bayesian persuasion: being almost optimal and almost persuasive, Approximation of coNP sets by NP-complete sets, Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete, Compactly representing utility functions using weighted goals and the Max aggregator, Dimension and the structure of complexity classes, On the complexity of restoring corrupted colorings, The Shrinking Property for NP and coNP, The shrinking property for NP and coNP, On Usefulness of Information: Framework and NFA Case, Mixing, Communication Complexity and Conjectures of Gowers and Viola, Understanding PPA-completeness, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, On membership comparable sets, Revisiting Deutsch-Jozsa algorithm, Introduction to Testing Graph Properties, Modeling time criticality of information, Conjugacy classes, growth and complexity, Promise Problems on Probability Distributions, Randomness buys depth for approximate counting, Practic zero-knowledge proofs: Giving hints and using deficiencies, Separating complexity classes with tally oracles, Structure Versus Hardness Through the Obfuscation Lens, A framework for non-interactive instance-dependent commitment schemes (NIC), Promise problems solved by quantum and classical finite automata, Quantum finite automata: advances on Bertoni's ideas, Absolute results concerning one-way functions and their applications, Inseparability and strong hypotheses for disjoint NP pairs, Graph isomorphism is low for PP, On the reducibility of sets inside NP to sets with low information content, Parallelization of entanglement-resistant multi-prover interactive proofs, Graph Isomorphism is in SPP, On the complexity of entailment in existential conjunctive first-order logic with atomic negation, Unnamed Item, Unnamed Item, How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge, General Properties of Quantum Zero-Knowledge Proofs, An Equivalence Between Zero Knowledge and Commitments, On the relationship between statistical zero-knowledge and statistical randomized encodings, Assisted Problem Solving and Decompositions of Finite Automata, An oracle separating conjectures about incompleteness in the finite domain, How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge, Unions of Disjoint NP-Complete Sets, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Hard promise problems and nonuniform complexity, Simplified Derandomization of BPP Using a Hitting Set Generator, On the Average-Case Complexity of Property Testing, In a World of P=BPP, On the Complexity of Computational Problems Regarding Distributions, Introduction to Testing Graph Properties, Contemplations on Testing Graph Properties, On sets bounded truth-table reducible to $P$-selective sets, Monotonous and randomized reductions to sparse sets, Graph isomorphism is low for PP, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, A hierarchy based on output multiplicity, On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings, On the limits of nonapproximability of lattice problems, A note on the non-NP-hardness of approximate lattice problems under general Cook reductions., A common algebraic description for probabilistic and quantum computations, Evaluation of exact quantum query complexities by semidefinite programming, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
