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 (67)
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 ⋮ NP-hardness of approximating meta-complexity: a cryptographic approach ⋮ Unnamed Item ⋮ Hardness and methods to solve CLIQUE ⋮ On computing optimal temporal branchings ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation ⋮ Is ML-based cryptanalysis inherently limited? Simulating cryptographic adversaries via gradient-based methods ⋮ On computing optimal temporal branchings and spanning subgraphs ⋮ 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
This page was built for publication:
