An NP-Complete Language Accepted in Linear Time by a One-Tape Turing Machine.
Pascal MichelPublished in: Theor. Comput. Sci. (1991)
Keyphrases
- turing machine
- np complete
- randomly generated
- np hard
- satisfiability problem
- high speed
- computational complexity
- language learning
- constraint satisfaction problems
- polynomial time complexity
- programming language
- natural language
- data complexity
- target language
- fixed parameter tractable
- conjunctive queries
- phase transition
- worst case
- artificial intelligence
- database