scientific article; zbMATH DE number 578252
From MaRDI portal
Publication:4293543
zbMath0809.68067MaRDI QIDQ4293543
Pierluigi Crescenzi, Daniel P. Bovet
Publication date: 29 May 1994
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
parallel computingparallel algorithmscomplexity theorycomplexity measurescomplexity classescomputing models
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)
Related Items (31)
It is hard to know when greedy is good for finding independent sets ⋮ On the efficiency of polynomial time approximation schemes ⋮ Query order in the polynomial hierarchy ⋮ A universal approach to guarantee data privacy ⋮ Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP ⋮ Universally serializable computation ⋮ Structure in approximation classes ⋮ The Helping Hierarchy ⋮ Max NP-completeness made easy ⋮ Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Approximate solution of NP optimization problems ⋮ If NP has polynomial-size circuits, then MA=AM ⋮ Helping by unambiguous computation and probabilistic computation ⋮ New collapse consequences of NP having small circuits ⋮ The navigational power of web browsers ⋮ On the autoreducibility of functions ⋮ A note on minimum-area upward drawing of complete and Fibonacci trees ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Complement for two-way alternating automata ⋮ If P \(\neq\) NP then some strongly noninvertible functions are invertible ⋮ Definability, decidability, complexity ⋮ Factorizing RSA keys, an improved analogue solution ⋮ A complexity analysis of bisimilarity for value-passing processes ⋮ Sets without subsets of higher many-one degree ⋮ 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 ⋮ Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. ⋮ Continuous One-counter Automata
This page was built for publication:
