FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 16 |

«Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

-- [ Page 6 ] --

3. Communicating Instances of Hard Problems In this chapter, we investigate a variant of the P vs. NP problem: We model the situation in which a time-bounded agent wants to solve a hard problem and is allowed to communicate with another, arbitrarily powerful agent. The catch is that the second agent does not know the description of the problem yet and can learn about it only by communicating with the first agent. We then ask how much communication is required for them to cooperatively solve the problem. Surely, the first agent can send the whole problem description so that the second agent can determine the answer. We find many problems for which this simple protocol is, in a complexity-theoretically precise sense, likely to be optimal: It is unlikely that they are able to solve the problem by using significantly less communication.

3.1. ORs of NP-hard problems All known kernel lower bounds for fixed-parameter tractable problems use – implicitly or explicitly – the fact that compressing ORs of NP-hard problems is impossible under standard complexity-theoretic assumptions. This fact is captured by Lemma 1.1, which we generalize to oracle communication protocols in this section.

Recall that ORt (L) is the problem of deciding whether at least one out of t(s) inputs, each of length s, belongs to L. The following lemma shows that low-cost protocols for ORt (L) can be used to build a proof system with advice for L.

Lemma 3.1 (Complementary Witness Lemma).

Let L be a language and t : N → N\{0} be polynomially bounded. If ORt (L) has an oracle communication protocol of cost O(t(s) log t(s)), where the first player can be conondeterministic, then L ∈ NP/poly.

Lemma 1.1 – the incompressibility of ORs of NP-hard problems under coNP ⊆ NP/poly– is a corollary of this lemma.

To see this, we observe that compressions give rise to lowcost protocols since the first player can just compress its input and then send it to the oracle. We now sketch the proof of Lemma 3.1 in the special case where the language L is P-selective. The simpler argument for that case provides a good starting point for the proof of the general case.

A P-selector for a language L is a polynomial-time algorithm that takes two instances x and y as input and outputs one of them, with the guarantee that if at least one of the inputs belongs to L then so does the output. Note that a P-selector for L immediately yields a low-cost oracle communication protocol for deciding OR(L) on inputs consisting of t instances of size s each – the first player uses the selector t − 1 times to determine

3. Communicating Instances of Hard Problems

which of the instances is “most likely” to be in L, sends that instance to the oracle, who responds with the membership of that instance to L. Since the cost of this protocol is s, any P-selective language satisfies the premise of Lemma 3.1 whenever t ≥ s.

Ko [Ko83] showed that the existence of a P-selector for L implies that L (and thus L) can be decided by circuits of polynomial size. The key insight is the following way to prove that an instance x belongs to L: Exhibit an instance y that is known to be in L and which the selector S outputs when given x and y as input. We call such a y a complementary witness. By viewing S on all pairs of a given subset F ⊆ L as a tournament, there always exists a y ∈ F that beats at least half of the x ∈ F and therefore can be used as a proof of membership of x to L. Starting from the set of all instances of size s in L, we repeatedly apply this procedure to the remaining set F of instances that have not yet been beaten by some of the y’s we picked, until the set becomes empty. This way, we obtain a collection As of at most s elements y such that x ∈ L if and only if there exists a y ∈ As such that S(x, y) = y. Using the set As as advice, this shows that L ∈ P/poly. If we allow the selector S to be nondeterministic (even multivalued), we similarly obtain that L ∈ NP/poly [HHN+ 95].

Fortnow and Santhanam [FS08] established the case of Lemma 3.1 where the protocol implements a ≤p -reduction from OR(L) to some language L such that t-tuples consistm ing of instances of bitlength s are mapped to an instance of bitlength bounded by some fixed polynomial in s, independent of t. Their proof can be viewed as an extension of the above argument. The witnesses y are now elements from L, and the requirement on the bitlength of the reduced instances guarantees that sufficiently popular y’s exist, so we do not need too many of them. The statement of Lemma 3.1 results from a more careful analysis of that argument for size bounds that can grow slowly with t, and from the extension to the general setting of our oracle communication protocols.

Proof (of Lemma 3.1). Let us first consider the case of a deterministic oracle communication protocol P modeled by a deterministic polynomial-time Turing machine M and a function f (see §2 for the notation). In this proof we make use of the notion of a communication transcript on a given input x. Such a transcript consists of the sequence of all queries P makes on input x (i.e., the contents of M ’s oracle query tape at the end of the protocol) as well as the answers f (q) to each of the oracle queries q.

The key ingredient of the proof is the following equivalence: An instance x of length s is in L if and only if there exists a sequence x2,..., xt(s) of instances of length s such that P (x, x2,..., xt(s) ) rejects. Here we can view the sequence (x, x2,..., xt(s) ) as an unordered sequence since we can assume w.l.o.g. that P sorts the t instances lexicographically before its actual computation starts. By including a large enough set As of communication transcripts and the value of t(s) as advice, this leads to the following

proof system with advice for L. On input an instance x of length s:

–  –  –

2. Check whether there is a communication transcript τ in As that is consistent with P on input (x, x2,..., xt(s) ) and that P (x, x2,..., xt(s) ) rejects. If so, accept;

otherwise, reject.

–  –  –

The check for a given transcript τ involves simulating the first player on the input (x, x2,..., xt(s) ). Whenever the first player sends a bit to the second player (by writing on the oracle query tape), verify that it agrees with the corresponding bit in τ. Whenever the first player expects a bit from the second player (by reading from the oracle answer tape), use the corresponding bit in τ. This process continues until a discrepancy is detected or the first player halts.

This proof system is sound as long as all communication transcripts in As are consistent with the protocol P. All that remains to show is the existence of a small subset As of such transcripts that guarantees completeness.

We construct the advice set As for a fixed s in the following greedy way. Consider instances x1,..., xt(s) of L of length s, and let T (x1,..., xt(s) ) denote the communication transcript of P on input (x1,..., xt(s) ). Since the second player is not given the input (x1,..., xt(s) ), the transcript T (x1,..., xt(s) ) is determined solely by the bits sent from the first player to the second player. Therefore, the number of distinct such transcripts is less than 2c(s)+1, where c(s) denotes the cost of the protocol on inputs consisting of t(s) instances of length s each. We say that a rejecting transcript τ covers an instance x ∈ L of length s if there exists a sequence x2,..., xt(s) of instances of length s each such that T (x, x2,..., xt(s) ) = τ. We start with As empty and successively pick a rejecting communication transcript τ that covers the largest number of instances x ∈ L of length s that are not covered thus far, and add τ to As. We keep doing so until there are no more instances x ∈ L of length s left to cover.

Consider one step in the construction of As and let F denote the set of uncovered instances x ∈ L of length s at the beginning of the step. Since every tuple in F t(s) is mapped by T to one of the rejecting transcripts above and there are less than 2c(s)+1 distinct such transcripts, there exists a rejecting transcript τ ∗ such that at least a fraction 1/2c(s)+1 of the tuples in F t(s) are mapped by T to this particular τ ∗, i.e., |T −1 (τ ∗ ) ∩ F t(s) | ≥ |F |t(s) /2c(s)+1. Now, each component of each tuple in T −1 (τ ∗ ) ∩ F t(s) is covered by τ ∗ since we can regard the tuples as unordered sequences. Thus, if we let G denote the subset of F that is covered by τ ∗, we have that T −1 (τ ∗ ) ∩ F t(s) ⊆ Gt(s). We conclude that |G|t(s) ≥ |T −1 (τ ∗ ) ∩ F t(s) | ≥ |F |t(s) /2c(s)+1, whence |G| ≥ ϕ(s) · |F | where ϕ(s) = 1/2(c(s)+1)/t(s).

Thus, every step covers a fraction at least ϕ(s) of the remaining instances to be covered.

Since there are at most 2s instances of length s to begin with, after steps there are no more than (1 − ϕ(s)) · 2s ≤ exp(−ϕ(s) ) · 2s instances left to cover, so the process ends after O(s/ϕ(s)) steps. Now, 1/ϕ(s) = 2(c(s)+1)/t(s) is polynomially bounded in t(s) as long as c(s) = O(t(s) log t(s)). Since each transcript as well as the running time of the proof system are polynomially bounded in s and t(s), for polynomially bounded t(s) the resulting algorithm for L runs in NP/poly.

This finishes the proof for the case of deterministic protocols P. For conondeterministic protocols we can define T (x1,..., xt(s) ) to be an arbitrary transcript of an execution on which P produces the correct output. The check in step 2 now involves nondeter


3. Communicating Instances of Hard Problems

minism. The fact that P has no valid rejecting executions for inputs (x1,..., xt(s) ) in OR(L) guarantees the soundness of the proof system, and the existence of at least one valid rejecting execution of P on an input (x1,..., xt(s) ) outside of OR(L) guarantees completeness. The counting argument carries over verbatim.

3.2. Vertex Cover In this section we establish Theorem 1.2 – that d-Vertex Cover has no oracle communication protocol of cost O(nd− ) for any positive constant unless coNP ⊆ NP/poly, where n represents the number of vertices of the d-uniform hypergraph. For ease of exposition we actually develop the equivalent result for d-Clique rather than for d-Vertex Cover. Theorem 1.2 then follows by hypergraph complementation.

We follow the approach outlined in the introduction: We assume that d-Clique has a protocol of low cost and we come up with a suitable reduction from the OR of an NP-hard language L to d-Clique to devise a low-cost protocol for the OR-problem.

We then invoke the complementary witness lemma and obtain that coNP ⊆ NP/poly if the cost of the assumed protocol for d-Clique was too small. The choice of L does not matter, and we pick it to be 3-Sat for convenience. The following lemma provides us with a reduction that is sufficient to obtain our tight results.

–  –  –

Before we delve into the proof of this lemma, let us first formally derive Theorem 1.2.

Theorem 1.2 (restated).

Let d ≥ 2 be an integer and a positive real. If coNP ⊆ NP/poly, there is no protocol of cost O(nd− ) to decide whether a d-uniform hypergraph on n vertices has a vertex cover of at most k vertices, even when the first player is conondeterministic.

Proof. Suppose d-Vertex Cover on n-vertex graphs has a protocol of cost O(nc ) for some constant c d. Let L denote 3-Sat. By combining the reduction from Lemma 3.2 with the standard reduction from d-Clique to d-Vertex Cover (mentioned in the preliminaries) and running the above protocol for d-Vertex Cover on the result of the combined reduction, we obtain a protocol for OR(L) of cost O(nc ) = O((s · max(s, t1/d+o(1) ))c ). Since c d the latter expression is O(t(s)) for sufficiently large polynomials t(s). Lemma 3.1 then shows that 3-Sat is in coNP/poly, which is equivalent to coNP ⊆ NP/poly.

For the reduction in Lemma 3.2, we are given t 3-CNF formulas ϕ1,..., ϕt, and we need to construct a d-uniform hypergraph G on few vertices n and an integer k such that at least one of the ϕi ’s is satisfiable if and only if G has a clique of size at least k.

We have two independent constructions that achieve an asymptotically optimal bound on the number of vertices n.

3.2. Vertex Cover

Elementary Proof We present an elementary reduction from OR(3-Sat) to d-Clique whose basic structure reappears in our lower bounds for packing problems in §3.5. In this reduction we actually achieve a bound of t1/d · poly(s) on the number of vertices, so we do not need to use the additional o(1)-slack in the exponent of t.

Proof (of Lemma 3.2). Let ϕ1,..., ϕt be the t instances of 3-Sat. Without loss of generality, assume that each formula has exactly p = s clauses, each consisting of a sequence of 3 literals. Let P and K1,..., Kt be the hypergraphs provided by Lemma 3.3.

Along the lines of the standard reduction from 3-Sat to 2-Clique by Karp [Kar72], we first translate the 3-CNF formulas ϕi into d-uniform hypergraphs Gi on the vertex sets V (Ki ) × [3]. For each i, we identify the elements of V (Ki ) × [3] with (positions of) literals of ϕi : The first component selects a clause from ϕi and the second component selects a literal from the clause. We let Gi be the d-uniform hypergraph with as edges all subsets e ⊆ V (Ki ) × [3] of size d such that no two elements of e correspond to the same clause ϕi or represent complementary literals. Note that each such e induces a satisfying assignment of the conjunction of the d clauses touched by e, and that Gi has a clique of size s if and only if ϕi is satisfiable.

Let G be the union of the Gi ’s, that is, the graph with V (G) = i∈[t] V (Gi ) ⊆ V (P ) × [3] and E(G) = i∈[t] E(Gi ). If ϕi has a satisfying assignment, then Gi has a clique of size s and so has G. For the other direction, let K be a clique of size s in G. The projection K of K onto the first component is a clique of size s in P. By property (ii) of Lemma 3.3, K = Ki for some i ∈ [t]. Moreover, by property (i) of Lemma 3.3, the projections of E(Gi ) and E(Gj ) for j = i are disjoint. It follows that K is a clique of size s in Gi, and therefore ϕi is satisfiable.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 16 |

Similar works:

«Commodity Futures Trading Commission Office of Public Affairs Three Lafayette Centre 1155 21st Street, NW Washington, DC 20581 www.cftc.gov CFTC Division of Market Oversight Responds to Frequently Asked Questions Regarding Commodity Options Commodity Options FAQs1 1. How are commodity options treated under the Commodity Exchange Act (“CEA” or “Act”), as amended by the Dodd-Frank Act? Section 721 of the Dodd-Frank Act added new § 1a(47) to the CEA defining “swap” to include “[an]...»

«New York City Guide to Solar on Existing School Buildings Contents Solar Technologies Solar Photovoltaic (PV): Solar Thermal (ST): Educational Opportunitities Educational Courses Installation Planning Requirements and Considerations: Upfront Costs building retrofits and initial installation Viable Roof & Schoolyard Space Existing Roof Condition Structural Loading Capacity Wind Load Analysis Equipment Maintenance and Fire Department Access Paths Egress from the Roof ADA Requirements Using Roof...»

«AIFS Study Abroad OutcOmes A view F rOm Our Alumni 1990 – 2010 AmericAn institute FOr FOreign study ® Copyright © 2013 American Institute For Foreign Study® All Rights Reserved. Contents 1 Introduction 5 Executive Summary 6 Survey Highlights 9 Program Impact 10 Outcomes 14 25 Years Later. 17 Next Steps: Innovating for the Future 19 Appendices 19 Response Results – Demographics, etc. 21 Travel-Related Questions 22 Foreign Language Study 23 Programs Represented in the Survey Responses...»

«293 Dezentrierung und Verkippung der neuen TecnisZCB00-Intraokularlinse im Vergleich mit der Linsenposition im jugendlichen Auge U. Mester, T. Sauer, H. Kaymak Zusammenfassung Hintergrund: Bekanntermaßen beeinträchtigen Verkippung und Dezentrierung von Intraokularlinsen (IOL) die Abbildungsqualität des Auges. Dies gilt im Besonderen für asphärische IOLs. In einer prospektiven Untersuchung wurden daher Verkippung und Dezentrierung der einstückigen asphärischen Tecnis IOL (ZCB00) gemessen...»

«Pay-to-fly: a multi-faceted problem Nienke Groenendijk-Feenstra, science journalist The airline pilot’s profession has always been glamourous. Most people think pilots have an exciting job, always make wonderful trips and also get paid extremely well. The general consensus is that being a pilot is a dream job, having the world literally at your feet. Unfortunately this image has changed radically over the last years, except for the select group of pilots who have a permanent contract with an...»

«Willdenowia 34 – 2004 411 doi:10.3372/wi.34.34208 (available via http://dx.doi.org/) JOS VAN DER MAESEN & AKPOVI AKOÈGNINOU Notulae Florae Beninensis 3. – Botanical collectors in Benin Abstract Van der Maesen, L. J. G. & Akoègninou, A.: Notulae Florae Beninensis 3. – Botanical collectors in Benin. – Willdenowia 34: 411-420. – ISSN 0511-9618; © 2004 BGBM Berlin-Dahlem. A list of botanists who have worked in Benin and made collections is provided. Biographical data, the number of...»

«Διδακτορική διατριβή της Ecole Doctorale des Sciences de la Terre (ED 109 – IPGP – Paris VII – ENS) και του Πανεπιστημίου της Πάτρας Παναγιώτης Ηλίας, MSc Για τον τίτλο του διδάκτορα της Ecole Normale Supérieure, Γαλλία και του πανεπιστημίου της Πάτρας στο πεδίο των Γεωεπιστημών Παρατηρούμενες εδαφικές...»

«CURRICULUM VITAE Chirayath M. Suchindran Addresses: Home: Office: 3103A McGavran-Greenberg Hall 8608 Yorkshire Lane Chapel Hill, NC 27516 University of North Carolina at Chapel Chapel Hill, NC 27599-7400 Telephone: (919) 929-3835 (919)966-7258 Citizenship: U.S. Citizen EDUCATION: University of Kerala, India B.Sc. 1960 Mathematics University of Kerala, India M.Sc. 1962 Statistics University of North Carolina MSPH 1968 Biostatistics at Chapel Hill University of North Carolina Ph.D. 1972...»

«Rürup-Rente 1 Rürup-Rente Die Basisrente, umgangssprachlich als Rürup-Rente nach dem Ökonomen Bert Rürup bezeichnet, ist eine Form der seit 2005 staatlich geförderten Altersvorsorge. Sie beruht auf einem Rentenversicherungsvertrag, der in den Leistungskriterien und der steuerlichen Behandlung weitgehend der gesetzlichen Rente entspricht;[1] allerdings ist die Basisrente nicht umlagefinanziert, sondern kapitalgedeckt. Im Unterschied zur klassischen privaten Rentenversicherung gibt es...»


«SCHOOL OF EARTH AND SPACE EXPLORATION, ARIZONA STATE UNIVERSITY ! P.O. BOX 876004 ! TEMPE, AZ 85287-6004 ! PHONE: 1 (970) 901–3580 ! E-MAIL: CAMERON.M.MERCER@ASU.EDU CAMERON M. MERCER EDUCATION 2011–Present Arizona State University, Tempe AZ School of Earth and Space Exploration Ph.D. Candidate — GPA: 4.0 Summer 2011 Fort Lewis College, Durango CO Geology Field Camp — GPA: 4.0 2007–2011 Middlebury College, Middlebury VT B.A. Physics and Geology — GPA: 3.61 Magna Cum Laude, High...»

«PROTOCOL OF AMENDMENT TO THE INTERNATIONAL CONVENTION ON THE SIMPLIFICATION AND HARMONIZATION OF CUSTOMS PROCEDURES OF 18 MAY 1973 (Brussels, 26 June 1999) The Contracting Parties to the International Convention on the Simplification and Harmonization of Customs Procedures (done at Kyoto on 18 May 1973 and entered into force on 25 September 1974), hereinafter the Convention, established under the auspices of the Customs Co-operation Council, hereinafter the Council, CONSIDERING that to achieve...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.