BOUNDED TILING, an alternative to SATISFIABILITY ?
Martin W. P. Savelsbergh, van P. Emde Boas · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1984
The BOUNDED TILING problem is presented and the question is raised whether it provides a viable alternative for the foundation of NP-completeness theory.To answer this question we take the standard results and investigate how they will look when they are based upon BOUNDED TILING.