<i>P</i> ≠ <i>NP</i> for all infinite Boolean algebras (Q4804182)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1896671
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | <i>P</i> ≠ <i>NP</i> for all infinite Boolean algebras |
scientific article; zbMATH DE number 1896671 |
Statements
<i>P</i> ≠ <i>NP</i> for all infinite Boolean algebras (English)
0 references
10 April 2003
0 references
P-NP-problem
0 references
computability over algebraic structures
0 references
infinite Boolean rings
0 references
0.8834301
0 references
0 references
0.8512558
0 references
0.8494469
0 references
0.8483841
0 references
0.84764206
0 references
Having given a ring \(R\), an input over \(R\) is a finite non-empty sequence of elements of \(R\). Let \(R^{\infty}\) be the set of all inputs. An \(R\)-machine is a computation system given by a finite description and able to work out inputs of arbitrary length according to a program. Binary nondeterminism is a nondeterminism which allows that in some situations the machine can continue its computation in two different ways and the decision is taken arbitrarily. Guess-nondeterministic machines have guess instructions, assigning to some register any value picked up from the ring. The classes \(\text{NBP}_R\) and \(\text{NP}_R\) are defined as the classes of problems recognized by the eventual halting of binary nondeterministic \(R\)-machines and guess-nondeterministic \(R\)-machines, respectively, in polynomial time; the class \(\text{P}_R\) is the class of problems decided by deterministic \(R\)-machines in polynomial time. Of course we have \(\text{P}_R \subseteq \text{NBP}_R \subseteq \text{NP}_R\). The main result in the paper states that all infinite Boolean rings \(R\) have the property \(\text{P}_R \not= \text{NBP}_R\) and, consequently, \(\text{P}_R \not=\text{NP}_R\). The proof is given in three steps (in three lemmas): elimination of constants, reduction of the problem to the existence of some uniform algorithm for all finite Boolean rings, and showing that such an algorithm does not exist.
0 references