| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9501280 | Journal of Complexity | 2005 | 22 Pages |
Abstract
Over the universe of binary words, {0,1}*, a type of structures of finite signature is defined that satisfy P=NP. This holds true both for the related classes of programs in which tests of equality (identity) of words are allowed, as well as for those in which no equality tests occur. The related structures correspond essentially to the pushdown data structures enriched by predicates which are suitably padded PSPACE-complete word sets.
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Armin Hemmerling,