New answers tagged

2 votes

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

Yes, via Ordinary Differential Equations. Bournez et al. described a connection between Turing Machines and Ordinary Differential Equations (ODE). Such connection preserves the notion of polynomiality ...
HeMath's user avatar
  • 21
5 votes
Accepted

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

[EDIT: This result was already observed in Corollary 4.6 of the following paper: Gajser, David, Verifying time complexity of Turing machines, Theor. Comput. Sci. 600, 86-97 (2015). ZBL1329.68111.] ...

Top 50 recent answers are included