Izrek o verjetnostnem preverjanju dokazov

Abstract

Keywords

Data

Language:	Slovenian
Year of publishing:	2011
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[A. Homar]
UDC:	519.2(043.2)
COBISS:	8611412
Views:	53
Downloads:	3
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	The PCP theorem
Secondary abstract:	Solutions to NP-problems are deterministically verifiable in polynomial time. But the classic verification process has a drawback - typically we need to (at least) read the entire proof to decide whether the proof is correct or incorrect. In the thesis we present the PCP theorem which claims that solutions to NP- problems can be checked by only a small number of queries to bits in their corresponding proof strings. We describe the equivalent version of the theorem which is at the heart of many approximation results for NP-hard problems. We illustrate this on two well-known problems, the maximum independent set problem and the minimum vertex cover problem. We present the main ideas of both versions of the PCP theorem proof: the original algebraic proof and later combinatorial version. In the last chapter we list some exciting discoveries related to the probabilistic checking of proofs.
Secondary keywords:	computational complexity;probabilistic checking of proofs;hardness of approximation;approximation algorithms;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
File type:	application/pdf
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	40 str.
ID:	23960193