No label defined (Q3341896)

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 3876591
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3876591

      Statements

      1984
      0 references
      tiling
      0 references
      computational complexity
      0 references
      unconstrained limited domino problem
      0 references
      nondeterministic exponential time complete
      0 references
      decision problem of predicate calculus
      0 references
      0 references
      [For the entire collection see Zbl 0538.00005.] Given a positive integer k, a finite set T (of different kinds of tiles) and two binary relations \(H,V\subseteq T\times T,\) the unconstrained limited domino problem asks the following question. Is it possible to cover a \(k\times k\) chess board with tiles, when tiles of type t' are allowed to lie to the right (below) tiles of type t only if H(t,t') (resp. V(t,t'))? The known undecidability proof for the unlimited (infinite board) domino problem suggests the limited problem with k given in binary (k big) still to be in NP (which has been known for k in unary notation). But the problem is shown to be nondeterministic exponential time complete. As a consequence the \(\forall\exists \wedge\forall \forall\) class of the decision problem of predicate calculus, without equality and function symbols, has a nondeterministic time complexity between \(c^{n/\log n}\) and \(d^{n/\log n}\) for some constants \(c,d>1.\)
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references