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
2 votes

deciding $\beta$-equality of planar lambda terms

If this proof sketch turns out to be correct, then β-equality of planar λ-terms is still P-complete. (Joint work by Anupam Das, Damiano Mazza, Noam Zeilberger and me; it's not yet peer-reviewed, and ...
Lê Thành Dũng 'Tito' Nguyễn's user avatar

Top 50 recent answers are included