TO KRDB
TO KRDB GROUP
if you are interested, I can give
4-hour tutorial (2 and 2) on "PCP theorem, Interactive Proofs and Inapproximability of Optimization Problems"
This talk would be more a tutorial, then a seminar. Full proofs, explanations and background materials will be given. I have given it once already in UoQ and this tutorial is quite ready in sense of quality of presentation.
PCP theorem is considered to be one of the major development in TCS in 90s. Perhaps, since 1992 every STOC and FOCS conference has at least one article strongly related to the PCP theorem.
Basically the PCP theorem provides a new characterization of NP class as a class of languages, a membership problem of which can be solved by the logarithmic number of random bits and the constant number of proof bits. (sounds miracle? The constant number of bits is actually needed instead of polynomial to proof a membership of the word.)
The original proof based on algebraic technique is quite complicated (around 20 pages of proof). The new proof based on combinatorial techniques (zig-zag products) was discovered this year by Irit Dinur.
Using other version of interactive proof systems we can capture PSPACE and NEXPTIME class and investigate some interesting properties of them.
NPO means NP optimization problem. NPO is a search version of NP class which is defined to be a class of decission problems. The NPO problem required to find a minimal (or maximal) solution among given one. For example, a Traveling Salesman Problem expressed as a search problem (Find a minimal lengh route in the graph which visit all vertices ones) would be an example of NPO problem. Usually NPO problem, a search version of NP decission problems belongs to FP^NP or FP^NP(log n) - hard classes indeed.
Since assuming P is not equal NP, there does not exist a polynomial algorithm to solve EXACTLY NP-hard-problems, given a NP-hard NPO problem it would be natural to ask, if a polynomial-time algorithm exists which can solve a problem with some approximation quality.
It was discovered that there exists a few approximation classes of NPO problems, which put certain bounds on approximation quality of algorithms for those problems.
PCP theorem is useful to prove in-approximation properties of NPO problems.
if you are interested, I can give
4-hour tutorial (2 and 2) on "PCP theorem, Interactive Proofs and Inapproximability of Optimization Problems"
This talk would be more a tutorial, then a seminar. Full proofs, explanations and background materials will be given. I have given it once already in UoQ and this tutorial is quite ready in sense of quality of presentation.
PCP theorem is considered to be one of the major development in TCS in 90s. Perhaps, since 1992 every STOC and FOCS conference has at least one article strongly related to the PCP theorem.
Basically the PCP theorem provides a new characterization of NP class as a class of languages, a membership problem of which can be solved by the logarithmic number of random bits and the constant number of proof bits. (sounds miracle? The constant number of bits is actually needed instead of polynomial to proof a membership of the word.)
The original proof based on algebraic technique is quite complicated (around 20 pages of proof). The new proof based on combinatorial techniques (zig-zag products) was discovered this year by Irit Dinur.
Using other version of interactive proof systems we can capture PSPACE and NEXPTIME class and investigate some interesting properties of them.
NPO means NP optimization problem. NPO is a search version of NP class which is defined to be a class of decission problems. The NPO problem required to find a minimal (or maximal) solution among given one. For example, a Traveling Salesman Problem expressed as a search problem (Find a minimal lengh route in the graph which visit all vertices ones) would be an example of NPO problem. Usually NPO problem, a search version of NP decission problems belongs to FP^NP or FP^NP(log n) - hard classes indeed.
Since assuming P is not equal NP, there does not exist a polynomial algorithm to solve EXACTLY NP-hard-problems, given a NP-hard NPO problem it would be natural to ask, if a polynomial-time algorithm exists which can solve a problem with some approximation quality.
It was discovered that there exists a few approximation classes of NPO problems, which put certain bounds on approximation quality of algorithms for those problems.
PCP theorem is useful to prove in-approximation properties of NPO problems.
posted by alopatenko at 10:05 AM
<< Home