東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Time and space in proof complexity.

Beck, Christopher.

FindBook

Google Book

Amazon

博客來

Time and space in proof complexity.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Time and space in proof complexity./
作者:	Beck, Christopher.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2017,
面頁冊數:	179 p.
附註:	Source: Dissertation Abstracts International, Volume: 78-07(E), Section: B.
Contained By:	Dissertation Abstracts International78-07B(E).
標題:	Computer science. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10249192
ISBN:	9781369557510

Time and space in proof complexity.
Beck, Christopher.

Time and space in proof complexity. - Ann Arbor : ProQuest Dissertations & Theses, 2017 - 179 p.

Source: Dissertation Abstracts International, Volume: 78-07(E), Section: B.

Thesis (Ph.D.)--Princeton University, 2017.

In this thesis we explore the limitations of efficient computation by way of the complexity of proofs.

ISBN: 9781369557510Subjects--Topical Terms:

523869
Computer science.

Time and space in proof complexity.
LDR:03141nmm a2200337 4500 001 2122578
005 20170922124928.5
008 180830s2017 ||||||||||||||||| ||eng d
020 $a 9781369557510
035 $a (MiAaPQ)AAI10249192
035 $a AAI10249192
040 $a MiAaPQ $c MiAaPQ
100 1 $a Beck, Christopher. $3 3183790
245 1 0 $a Time and space in proof complexity.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2017
300 $a 179 p.
500 $a Source: Dissertation Abstracts International, Volume: 78-07(E), Section: B.
500 $a Adviser: Sanjeev Arora.
502 $a Thesis (Ph.D.)--Princeton University, 2017.
520 $a In this thesis we explore the limitations of efficient computation by way of the complexity of proofs.
520 $a One of the goals of theoretical computer science is to understand algorithms broadly---to identify meta-algorithms that may be useful in a variety of cases, understand how they work, when they work well, and when they don't.
520 $a For several important groups of algorithms, there is a relatively simple mathematical proof that the algorithm is correct for every input. Moreover, when the algorithm is run on any particular input, this proof specializes to produce a very simple combinatorial proof of the correct answer for that input. A simple example is a linear program, which may find an optimal point and give a dual solution proving the optimality, or a graph search algorithm which may fail to find a path between two points and yield a cut separating them instead.
520 $a Often times, self-contained proofs that the answer to some query is yes or no are just as important as the answer itself. When the algorithm is meant to identify problems in some system, or opportunities, the proof may actually represent actionable information in some domain. A good example is when a SAT solver is used to validate a system that is being designed. When the validation fails, the proof indicates where the problem is with the current design.
520 $a Proof complexity attempts to place limits on how efficient such algorithms can be by showing that these proofs must sometimes be very complex, growing rapidly as the problem scales up. More broadly, proof complexity attempts to understand the proving power of traditional formal systems for logic, and to corroborate hypotheses like P != NP. We develop novel combinatorial techniques for studying proof complexity in several well-studied proof systems.
520 $a We give substantial quantitative improvements on existing results, and also, develop a new method that allows us to study the time and space needed for a proof simultaneously and prove "tradeoff'' lower bounds. We show that small reductions in space can sometimes lead to large increases in time, even in situations where the algorithm has large amounts of space to work with. Previously no such results were known in that situation.
590 $a School code: 0181.
650 4 $a Computer science. $3 523869
690 $a 0984
710 2 $a Princeton University. $b Computer Science. $3 2099280
773 0 $t Dissertation Abstracts International $g 78-07B(E).
790 $a 0181
791 $a Ph.D.
792 $a 2017
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10249192