CS proofs 论文
2002引用 276
Cryptography and Data SecurityComplexity and Algorithms in Graphssemigroups and automata theory
详细信息
- 发表日期
- 2002-12-17
- 发表年份
- 2002
关键词
Cryptography and Data SecurityComplexity and Algorithms in Graphssemigroups and automata theory
摘要
This paper puts forward a computationally-based notion of proof and explores its implications to computation at large. In particular, given a random oracle or a suitable cryptographic assumption, we show that every computation possesses a short certificate vouching its correctness, and that, under a cryptographic assumption, any program for a /spl Nscr//spl Pscr/-complete problem is checkable in polynomial time. In addition, our work provides the beginnings of a theory of computational complexity that is based on "individual inputs" rather than languages.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>