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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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:
