<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
      0 references
      10 April 2003
      0 references
      P-NP-problem
      0 references
      computability over algebraic structures
      0 references
      infinite Boolean rings
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references