Izrek o verjetnostnem preverjanju dokazov

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2011
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[A. Homar]
UDK:	519.2(043.2)
COBISS:	8611412
Št. ogledov:	53
Št. prenosov:	3
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The PCP theorem
Sekundarni povzetek:	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.
Sekundarne ključne besede:	computational complexity;probabilistic checking of proofs;hardness of approximation;approximation algorithms;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo/naloga
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	40 str.
ID:	23960193