University of Cambridge > Talks.cam > CQIF Seminar > Too Good to be True? Precisely! The Real Cost of Non-Standard Computation

Too Good to be True? Precisely! The Real Cost of Non-Standard Computation

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Paul Skrzypczyk.

Certain (unconventional, non-Turing) computers give the illusion of efficiency, whilst being fundamentally impracticable. The illusion stems from the computers’ polynomial time and space complexity, the impracticability from their exponential complexity with respect to computational resources other than time and space (precision, for example, is such a resource). From previous research, we recap a paradigm- and resource-independent framework of computational complexity that dispels this illusion. From immanent research, we mention an application of the framework to Shor’s algorithm (the question here is ‘what is the precision complexity of Shor’s algorithm?’). And from proposed research, we describe an extension of the framework from complexity-theoretic to cryptographic concerns.

This talk is part of the CQIF Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2022 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity