scientific article
From MaRDI portal
Publication:4071737
zbMath0313.02026MaRDI QIDQ4071737
Publication date: 1973
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Computational depth: Concept and applications, On search, decision, and the efficiency of polynomial-time algorithms, A denial-of-service attack on fiber-based continuous-variable quantum key distribution, How to prove representation-independent independence results, Towards a unified approach to black-box constructions of zero-knowledge proofs, Sophistication revisited, Time hierarchies for cryptographic function inversion with advice, In some curved spaces, one can solve NP-hard problems in polynomial time, Fixed-Parameter Tractability, A Prehistory,, Computing equilibria: a computational complexity perspective, Autonomous theory building systems, A faster distributed protocol for constructing a minimum spanning tree, An excursion to the Kolmogorov random strings, Smoothing the Gap Between NP and ER, Satisfiability in Boolean Logic (SAT problem) is polynomial?, Deciding Parity Games in Quasi-polynomial Time, The discovery of algorithmic probability, The evolution of human communication and the information revolution --- A mathematical perspective, On relationships between complexity classes of Turing machines, Optimal design of switched Ethernet networks implementing the multiple spanning tree protocol, Fast probabilistic algorithms for Hamiltonian circuits and matchings, Physical portrayal of computational complexity, The complete set of minimal simple graphs that support unsatisfiable 2-CNFs, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality, Algebraic Attacks against Random Local Functions and Their Countermeasures, A note on the self-witnessing property of computational problems, Mathematics of computation through the lens of linear equations and lattices, Low-depth witnesses are easy to find, Unnamed Item, The complexity of problems for quantified constraints, Unnamed Item, Optimal algorithms for co-NP-sets and the EXP\(\overset{!}{ = }\)NEXP problem, Constructive complexity, Inverse monoids associated with the complexity class NP, Satisfiability modulo theories and chiral heterotic string vacua with positive cosmological constant, Diverse Palindromic Factorization is NP-Complete, Making sense of sensory input, On the theory of average case complexity, Self-witnessing polynomial-time complexity and prime factorization, Finite-model theory -- A personal perspective, Optimal testing for planted satisfiability problems, What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\), Lower bounds for non-black-box zero knowledge, Unnamed Item, Hardness and methods to solve CLIQUE, Parameterised complexity of model checking and satisfiability in propositional dependence logic, Unnamed Item, Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer, Notes on Levin’s Theory of Average-Case Complexity, A theory of incremental compression, On the Complexity of Local Graph Transformations, Randomness and Intractability in Kolmogorov Complexity, $$P\mathop{ =}\limits^{?}NP$$, Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search, On Khot’s unique games conjecture, A Logical Approach to Constraint Satisfaction, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Resource bounded symmetry of information revisited, Polynomial time computations in models of ET, On Dinur’s proof of the PCP theorem, Complexity questions in number theory
