P ≠ NP for all infinite Boolean algebras
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.
- P NP for infinite time Turing machines
- P ≠ NP ∩ co-NP for Infinite Time Turing Machines
- scientific article; zbMATH DE number 2163541
- Pf ≠ NPf for almost all f
- scientific article; zbMATH DE number 953010
- scientific article; zbMATH DE number 1421070
- On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
- The Nonapproximability of Non-Boolean Predicates
- The non-approximability of non-Boolean predicates
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- On the P-NP problem over real matrix rings
- Two situations with unit-cost: ordered abelian semi-groups and some commutative rings
- P ≠ NP ∩ co-NP for Infinite Time Turing Machines
- A model-theoretic proof for P ≠ NP over all infinite abelian group
- The path-bifurcation hierarchy does not collapse to ^1 in infinite abelian groups
- On the P=NP problem in some rings
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)