scientific article; zbMATH DE number 578252

MaRDI QIDQ4293543zbMATH OpenFDO

Authors Daniel P. Bovet, Pilu Crescenzi

Publication date 29 May 1994

zbMATH Keywords

complexity classescomplexity measurescomplexity theorycomputing modelsparallel algorithmsparallel computing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• Complexity science. An introduction
• Introduction to the theory of complex systems
• Complexity theory
• Complexity theory
• Complexity. A very short introduction
• The complexity theory companion

Cited in

(48)

• Factorizing RSA keys, an improved analogue solution
• Universally serializable computation
• Complexity theory. Limits of the efficiency of algorithms
• Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography.
• A complexity analysis of bisimilarity for value-passing processes
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Definability, decidability, complexity
• Some aspects of studying an optimization or decision problem in different computational models
• On the Hamming distance of constraint satisfaction problems.
• Tally NP sets and easy census functions.
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Max NP-completeness made easy
• Data independence of read, write, and control structures in PRAM computations
• A universal approach to guarantee data privacy
• If P \(\neq\) NP then some strongly noninvertible functions are invertible
• Sets without subsets of higher many-one degree
• It is hard to know when greedy is good for finding independent sets
• On the efficiency of polynomial time approximation schemes
• scientific article; zbMATH DE number 412149 (Why is no real title available?)
• scientific article; zbMATH DE number 4106275 (Why is no real title available?)
• scientific article; zbMATH DE number 43004 (Why is no real title available?)
• scientific article; zbMATH DE number 44418 (Why is no real title available?)
• scientific article; zbMATH DE number 1216160 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• The Helping Hierarchy
• scientific article; zbMATH DE number 1033441 (Why is no real title available?)
• Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
• Computational complexity on the blackboard
• New collapse consequences of NP having small circuits
• scientific article; zbMATH DE number 2167361 (Why is no real title available?)
• Abstract recursion and intrinsic complexity
• scientific article; zbMATH DE number 877979 (Why is no real title available?)
• Query order in the polynomial hierarchy
• Computational Complexity
• Algorithmic complexity
• Continuous One-counter Automata
• Complement for two-way alternating automata
• Structure in approximation classes
• Computability and complexity theory.
• Approximate solution of NP optimization problems
• If NP has polynomial-size circuits, then MA=AM
• Helping by unambiguous computation and probabilistic computation
• The navigational power of web browsers
• Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
• On the autoreducibility of functions
• A note on minimum-area upward drawing of complete and Fibonacci trees

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4293543)