P ≠ NP for all infinite Boolean algebras

From MaRDI portal
Publication:4804182





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.











This page was built for publication: P ≠ NP for all infinite Boolean algebras

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