Fast simulation of nondeterministic turing machines with application to the knapsack problem
Jiřı́ Wiedermann · 1989
A new, efficient simulation of a nondeterministic Turing machine by a deterministic one in time that is exponential w.r.t. the space complexity of the machine simulated is shown. As a consequence a deterministic Turing machine algorithm for the knapsack problem of time complexity O(c √n ) is designed