TY - GEN

T1 - The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)

AU - Fürer, Martin

N1 - Publisher Copyright:
© 1984, Springer-Verlag.

PY - 1984

Y1 - 1984

N2 - The unconstrained domino or tiling problem is the following. Given a finite set T (of tiles), sets H,V ⊑ T×T and a cardinal k ≤ ω, does there exist a function:k×k->T such that (t(i,j),t(i+1,j))εH and (t(i,j),t(i,j+1))εV for all i,jn) nondeterministic time lower bound (upper bound O(dn)). As a consequence, the non-deterministic time complexity of the decision problem for the Вε ВВ class of predicate calculus lies between Θ (cn/log n) and O(dn/log n).

AB - The unconstrained domino or tiling problem is the following. Given a finite set T (of tiles), sets H,V ⊑ T×T and a cardinal k ≤ ω, does there exist a function:k×k->T such that (t(i,j),t(i+1,j))εH and (t(i,j),t(i,j+1))εV for all i,jn) nondeterministic time lower bound (upper bound O(dn)). As a consequence, the non-deterministic time complexity of the decision problem for the Вε ВВ class of predicate calculus lies between Θ (cn/log n) and O(dn/log n).

UR - http://www.scopus.com/inward/record.url?scp=85034848491&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034848491&partnerID=8YFLogxK

U2 - 10.1007/3-540-13331-3_48

DO - 10.1007/3-540-13331-3_48

M3 - Conference contribution

AN - SCOPUS:85034848491

SN - 9783540133315

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 312

EP - 319

BT - Logic and Machines

A2 - Borger, E.

A2 - Hasenjaeger, G.

A2 - Rodding, D.

PB - Springer Verlag

T2 - Symposium on Rekursive Kombinatorik, 1983

Y2 - 23 May 1983 through 28 May 1983

ER -