𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Positive relativizations of the P = ? NP problem

✍ Scribed by Craig A. Rich

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
763 KB
Volume
38
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The STO problem is NP-complete
The STO problem is NP-complete
✍ P. Krysta; L. Pacholski πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 233 KB

We prove that the problem STO of deciding whether or not a finite set E of term equations is subject to occur-check is in NP. E is subject to occur-check if the execution of the Martelli-Montanari unification algorithm gives for input E a set E βˆͺ {x = t}, where t = x and x appears in t. Apt et al. (

The Relative Complexity of NP Search Pro
The Relative Complexity of NP Search Problems
✍ Paul Beame; Stephen Cook; Jeff Edmonds; Russell Impagliazzo; Toniann Pitassi πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 521 KB

Papadimitriou introduced several classes of NP search problems based on combinatorial principles which guarantee the existence of solutions to the problems. Many interesting search problems not known to be solvable in polynomial time are contained in these classes, and a number of them are complete

On the np-completeness of certain networ
On the np-completeness of certain network testing problems
✍ S. Even; O. Goldreich; S. Moran; P. Tong πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 946 KB

Let G ( V , E) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its endpoints t o be a transmitter, the other to be a receiver, and sen

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ JiΕ™Γ­ Fiala πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 63 KB πŸ‘ 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co