#P Closures: Witness Reduction Technique & Proper Subtraction
Explore the concept of #P closures under proper subtraction in computational theory through the Witness Reduction Technique. Learn how #P.P functions are defined and closed under certain operations, including examples of closures under addition and multiplication.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Chapter 5: The Witness Reduction Technique Joseph Cloud, Ashley Wilson, Mengqi Zhang April 19 & 24, 2023
Is #P closed under proper subtraction? Definition 8.2 Definition 8.2(#P P) #P P is the set of all functions : {0, 1}* such that there is a NPTM M such that for all x {0, 1}*, (x) = number of accepting branches in (x) = number of accepting branches in M M s computation graph on s computation graph on x x 3
Is #P closed under proper subtraction? Definition 8.2 Definition 8.2(#P P) #P P is the set of all functions : {0, 1}* such that there is a NPTM M such that for all x {0, 1}*, (x) = number of accepting branches in (x) = number of accepting branches in M M s computation graph on s computation graph on x x Proper Subtraction ( ) a b = max({0, a b}) 4
Is #P closed under proper subtraction? Definition 8.2 Definition 8.2(#P P) #P P is the set of all functions : {0, 1}* such that there is a NPTM M such that for all x {0, 1}*, (x) = number of accepting branches in (x) = number of accepting branches in M M s computation graph on s computation graph on x x Proper Subtraction ( Let be an operation from ? to and let ? be a class of functions from to . ) a b = max({0, a b}) We say that ? is closed under (the operation) if ( ( 1 1 ?)( )( 2 2 ?)[h )[hf ,f f ,f ?] ] 1 2 1 2 where hf ,f (?) = [ 1(?), 2(?) ] 1 2 5
Other #P Closures Example: #P P is closed under addition Example: #P P is closed under multiplication ? ? 6
Other #P Closures Example: #P P is closed under addition Example: #P P is closed under multiplication 7
Preliminary Definitions Predicate (does ? accept ? on ?) Polynomial length of path Certificates (paths in ?) { ? |?| q(|?|) R(?, ?)} 8
Preliminary Definitions Definition of UP Definition of UP A language L is in UP and a polynomial q such that for all ?, UP if there is a polynomial-time predicate R ||{ ? |?| q(|?|) R(?, ?)}|| = 0 if ? L 1 if ? L 9
Preliminary Definitions Definition of PP Definition of PP A language L is in PP polynomial-time predicate R such that for all ?, PP if there exists a polynomial q and a < 2q(|?|) 1if ? L 2q(|?|) 1if ? L ||{ ? |?| = q(|?|) R(?, ?)}|| = 10
Preliminary Definitions Definition of Definition of P P A language L is in P P if there exists a polynomial q and a polynomial-time predicate R such that for all ?, even if ? L odd if ? L ||{ ? |?| q(|?|) R(?, ?)}|| = 11
Witness Reduction Technique Witness? Adding is easy, removing is difficult Consequences of the possibility of removing witnesses Complexity class collapse Idea of the technique 12
Witness Reduction Technique L S1 S2 S1 to S1= S2 L S2 Coerce the function back into a machine defining a language in the smaller class (S2) Take some set in the larger class (S1) and coerce it into #P function N'L NL Application of Assumed Closure #P #P 13
Is #P closed under proper subtraction? Find a collapse that characterizes the closure Operator completeness for #P P 14
Is #P closed under proper subtraction? Theorem 5.6 Theorem 5.6 The following statements are equivalent 1. #P P is closed under proper subtraction. 2. #P P is closed under every polynomial-time computable operation 3. 3. UP UP = PP PP 15
Is #P closed under proper subtraction? Theorem 5.6 Theorem 5.6 The following statements are equivalent 1. #P P is closed under proper subtraction. 2. #P P is closed under every polynomial-time computable operation 3. 3. UP UP = PP PP 16
Is #P closed under proper subtraction? Theorem 5.6 Theorem 5.6 The following statements are equivalent 1. #P P is closed under proper subtraction. 2. #P P is closed under every polynomial-time computable operation 3. 3. UP UP = PP PP ? ? 17
Is #P closed under proper subtraction? Theorem 5.6 Theorem 5.6 The following statements are equivalent 1. #P P is closed under proper subtraction. 2. #P P is closed under every polynomial-time computable operation 3. 3. UP UP = PP PP ? ? 1. Closed (#?, ) 2. Closed (#?,??) (?? is any arbitrary polynomial-time computable operation) 3. UP = PP 18
Is #P closed under proper subtraction? Closed(#P P, ) UP UP = PP PP Closed(#P P, ) PP PP UP UP UP UP PP PP UP UP PP PP by direct proof 19
Is #P closed under proper subtraction? UP UP PP PP by direct proof 1. Let L be a UP language and let N be the NPTM that accepts L 2. Let N be a NPTM with the same depth, q(|?|), as N and accepts on all paths but one 1. Let NPPbe a NPTM that chooses between simulating N and N Computation Paths : 2q(|?|) + 1 Accepting Paths : 2q(|?|)(N : 1, N : 2q(|?|) 1) 20
Is #P closed under proper subtraction? Closed(#P P, ) UP UP = PP PP Closed(#P P, ) PP PP UP UP UP UP PP PP UP UP PP PP by direct proof Closed(#P P, ) PP PP UP UP Closed(#P P, ) PP PP CoNP NP CoNP NP UP UP 21
Is #P closed under proper subtraction? Closed(#P P, ) PP PP CoNP NP L PP L = { ? ||{ ? |?| = q(|?|) R(?, ?)}|| 2q(|?|) 1 } Let q (|?|) = q(|?|) + 1 and for b {0, 1}, R (?, ?b) = R(?, ?) and, for all ?, q(?) 1 (avoid q(|?|) = 0) 22
Is #P closed under proper subtraction? Closed(#P P, ) PP PP CoNP NP Let N be an NPTM that on input ? guesses each ? such that |?| = q(|?|) then tests R(?, ?) The #P P function defined by this NPTM has that ? L (?) 2q(|?|) 1 ? L (?) < 2q(|?|) 1 23
Is #P closed under proper subtraction? Is #P closed under proper subtraction? Closed(#P P, ) PP PP CoNP NP ?(?) = 2q(|?|) 1 1 is a #P P function By assumption of closure under proper subtraction ?(?) = ?(?) ?(?) is a #P P function, and by substituting yields ?(?) 1 ?(?) = 0 if ? L if ? L Clearly NP NP, but 24
Is #P closed under proper subtraction? Closed(#P P, ) PP PP CoNP NP There exists a NPTM N for which ? computes the number of accepting paths The values of ? are such that N is an NP machine, so the arbitrary PP PPlanguage is in NP NP It follows that PP PP PP= CoPP PP PP PP NP PP CoNP NP NP 25
Is #P closed under proper subtraction? Closed(#P P, ) CoNP NP UP UP Let L be an arbitrary CoNP NPlanguage There exists a NPTM N that accepts L N defines a #P P function such that ? L ?(?) = 0 ? L ?(?) 1 26
Is #P closed under proper subtraction? Closed(#P P, ) CoNP NP UP UP The constant function ?(?) = 1 is a #P P function By assumption of closure under proper subtraction ?(?) =?(?) ?(?) is a #P P function, and by substituting yields ?(?) = 1 if ? L ?(?) = 0 if ? L ? corresponds to a UP UP machine 27
Is #P closed under proper subtraction? Theorem 5.6 Theorem 5.6 The following statements are equivalent 1. #P P is closed under proper subtraction. 2. #P P is closed under every polynomial-time computable operation 3. 3. UP UP = PP PP ? ? 28
Is #P closed under proper subtraction? UP UP = PP PP Closed(#P P,??) 1. Let op be an arbitrary polynomial-time computable operation 2. Let ? and ? be arbitrary #P P functions B?= { ?, ? ?(?) ? } PP PP B?= { ?, ? ?(?) ? } PP PP 29
Is #P closed under proper subtraction? UP UP = PP PP Closed(#P P,??) 1. Let op be an arbitrary polynomial-time computable operation 2. Let ? and ? be arbitrary #P P functions B?= { ?, ? ?(?) ? } PP PP B?= { ?, ? ?(?) ? } PP PP V = { ?, ?1, ?2 ?, ?1 B? ?, ?1+ 1 B? ?, ?2 B? ?, ?2+ 1 B?} 30
Is #P closed under proper subtraction? UP UP = PP PP Closed(#P P,??) V gives precise values of ?(?) and ?(?) by testing adjacent ?s to find transition points in B?and B? V 4-truth-table reduces to the language B? B? denotes disjoin Union: ? ? = {0? ? ?} {1? ? ?} 31
Is #P closed under proper subtraction? UP UP = PP PP Closed(#P P,??) V gives precise values of ?(?) and ?(?) by testing adjacent ?s to find transition points in B?and B? Corollary Corollary9.17 table reductions and disjoint union V PP 9.17PP is closed under polynomial time bounded-truth- PP V UP UP by assumption that UP UP= PP PP 32
Is #P closed under proper subtraction? UP UP = PP PP Closed(#P P,??) ? and ? are #P P functions, so for some polynomial q and for all ? max{?(?), ?(?)} 2q(|?|) Consider the NP 1. Nondeterministically choose an integer ?, 0 ? 2q(|?|) 2. Nondeterministically choose an integer ?, 0 ? 2q(|?|) 3. Guesses a computation path of V on input ?, ?, ? . If the path rejects, reject. Otherwise, nondeterministically guess an integer ?, 1 ? op(?, ?) and accept. NPmachine N that on input ? 33
Is #P closed under proper subtraction? UP UP = PP PP Closed(#P P,??) For all ? = ?(?) and ? = ?(?), V( ?, ?, ? ) rejects For the correct ? and ?, N(?) accepts along precisely ??(?, ?) paths The #P P function defined by this machine is ?(?) = ??(?(?), ?(?)) 34
Is #P closed under proper subtraction? V ??(?, ?) 35
How Significant is the Collapse? Theorem 5.7 Theorem 5.7 The following statements are equivalent 1. 1. UP UP = PP PP 2. 2. UP UP= NP NP= CoNP NP= PH PH= P P = PP PPPP PP PP = PP PP PP 37
How Significant is the Collapse? Theorem 5.7 Theorem 5.7 The following statements are equivalent 1. 1. UP UP = PP PP 2. 2. UP UP= NP NP= CoNP NP= PH PH= P P = PP PPPP PP PP = PP PP PP Prove each of the above in sequence 38
How Significant is the Collapse? PPPP PP UP UP = NP NP PP PP NP = CoNP NP = PH PH = P P = PP PP = PP PP PP NP 1. Let L NP 2. Let N be a NPTM with the same depth, q(|?|), NP and let N be the NPTM that accepts L as N and accepts on all paths but one 1. Let NPPbe a NPTM that chooses between simulating N and N Computation Paths : 2q(|?|) + 1 Accepting Paths : 2q(|?|)(N : 1, N : 2q(|?|) 1) 39
How Significant is the Collapse? PPPP PP UP UP = NP UP NP NP PP NP = CoNP PP, UP UP = PP NP = PH PP UP PH = P P = PP UP = NP NP PP = PP PP PP UP 1. Let L NP 2. Let N be a NPTM with the same depth, q(|?|), NP and let N be the NPTM that accepts L as N and accepts on all paths but one 1. Let NPPbe a NPTM that chooses between simulating N and N Computation Paths : 2q(|?|) + 1 Accepting Paths : 2q(|?|)(N : 1, N : 2q(|?|) 1) 40
How Significant is the Collapse? PPPP PP UP UP = NP PP = CoPP NP = CoNP PP NP = PH PH = P P = PP PP = PP PP PP PP 1. Let L PP PPand let N be the NPTM that accepts L 2. Let N be equivalent to N, but ensuring the rightmost path rejects 3. Let NCoPP PPa NPTM that takes N and expands down one level For the rightmost leaf node of N , one child accepts and one rejects For accepting leaf nodes of N , both children reject For rejecting leaf nodes of N , both children accept 41
How Significant is the Collapse? PPPP PP UP UP = NP PP = CoPP NP = CoNP PP NP = PH PH = P P = PP PP = PP PP PP PP 1. Let L PP PPand let N be the NPTM that accepts L 2. Let N be equivalent to N, but ensuring the rightmost path rejects 3. Let ? be the number of accepting paths in N 4. Let ? 1 be the depth of N Rejecting Paths : 2? + 1 Accepting Paths : 2? + 1 2? 1 42
How Significant is the Collapse? PPPP PP UP UP = NP PP = CoPP NP = CoNP PP NP = PH PH = P P = PP PP = PP PP PP PP 1. Let L PP PPand let N be the NPTM that accepts L 2. Let N be equivalent to N, but ensuring the rightmost path rejects 3. Let ? be the number of accepting paths in N 4. Let ? 1 be the depth of N PP PP = CoPP PP, NP NP = PP PP NP NP = CoNP NP 43
How Significant is the Collapse? PPPP PP UP UP = NP NP = CoNP NP = PH PH= P P = PP PP = PP PP PP NPNP NP CoNP NP= NP NPNP NP = NP NP NP = CoNP NP NP NP PH PH= NP NP 44
How Significant is the Collapse? PPPP PP UP UP = NP NP = CoNP NP = PH PH= P P = PP PP = PP PP PP P PNP NP PH UP P PUP UP PH PH P PUP UP= UP PH, NP NP = UP PH, UP UP = PH UP 45
How Significant is the Collapse? PPPP PP UP UP = NP NP = CoNP NP = PH PH= P P = PP PP = PP PP PP P PNP Lemma 4.14 Lemma 4.14 PP NP PH UP P PUP PP P P P PPP UP PH PH P PUP UP= UP PP P P PH, NP NP = UP UP = PH UP, UP UP P P PP UP = P P PH, UP UP PP,P PPP UP PP = UP 46
How Significant is the Collapse? PPPP PP UP UP = NP NP = CoNP NP = PH PH= P P = PP PP = PP PP PP P PNP Lemma 4.14 Lemma 4.14 PP NP PH UP P PUP PP P P P PPP UP PH PPPP UP UP = P P PP PP PH P PUP UP= UP PP P P PH, NP NP = UP PH, UP UP = PH UP, UP UP P P PP UP PP,PP PP = UP PP P P= PP PPPP PP= PP PP P P= PP P P = PP PP, PP PPs of arbitrary height can be reduced to PP PP any stack of PP PP 47
More Witness Reduction Theorem 5.9 Theorem 5.9 The following statements are equivalent 1. #P P is closed under integer division 2. #P P is closed under every polynomial-time computable operation 3. 3. UP UP = PP PP Definition 5.8 Definition 5.8Let ? be a class of functions from to . We say that ? is closed under integer division ( ) if ( ?1 ?)( ?2 ? : ( ?)[?2(?) > 0])[?1 ?2 ?] 48
More Witness Reduction Theorem 5.9 Theorem 5.9 The following statements are equivalent 1. #P P is closed under integer division 2. #P P is closed under every polynomial-time computable operation 3. 3. UP UP = PP PP ? ? 49
More Witness Reduction Closed(#P P, ) UP UP = PP PP Let L be any PP PPset, there is a NPTM N and integer ? 1 such that ? 1. On each input ?, N(?) has exactly 2|?| computation paths, each containing |?|?binary choices, 2. On each input ?, ? L iff N(?) has at least 2|?| 1accepting paths, and 3. On each input ?, N(?) has at least one rejecting path. ? 50
