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.8717133
0 references
0 references
0.8679406
0 references
0.8653979
0 references
0.8600489
0 references
0.8593186
0 references
0.85653484
0 references
0.85583687
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