Skip to main content
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
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

Only top scored, non community-wiki answers of a minimum length are eligible