Subset sum

Bit-string encoding of SUBSET-SUM instances to Value of the empty bit list

• Bit-string encoding of SUBSET-SUM instances
• The SUBSET-SUM problem
• Place value of a vertex pair in the SUBSET-SUM reduction
• Pairs touching a vertex
• Vertex numbers of the SUBSET-SUM reduction
• Edge numbers of the SUBSET-SUM reduction
• Target of the SUBSET-SUM reduction
• Numbers of the SUBSET-SUM reduction
• Fixed no-instance of SUBSET-SUM
• Reduction from VERTEX-COVER to SUBSET-SUM
• The fixed no-instance of SUBSET-SUM
• Base-4 expansions with digits below \(4\) are unique
• Sublists of the reduction's numbers as vertex and pair sets
• A vertex number in base 4
• The target in base 4
• A subset sum of the reduction's numbers in base 4
• Vertices of a set touching a vertex pair
• Vertex covers in terms of the pair bits
• Vertex covers of size \(k\) match subset sums hitting the target
• Value of the empty bit list

Value of a bit list with a leading bit to Reading a pair bit or vertex mark

• Value of a bit list with a leading bit
• A bit list without trailing false is the binary code of its value
• Value of a list of two-bit digits
• Binary code of the value of a bit list
• Delimiting a bit list that ends in true
• Output block of a vertex-number digit
• Output block of an edge number
• Output of all edge numbers
• The pair walk over lists of marks
• Triangular numbers
• The pair walk lists the vertex pairs in reverse
• Vertex marks for a vertex
• Touch bits from the pair walk of a vertex
• Stacks of the SUBSET-SUM reduction machine
• Stack alphabets of the subset-sum emitter
• Labels of the subset-sum emitter
• Counter unit of the subset-sum emitter
• Test for the input bit true (SUBSET-SUM reduction machine)
• Test for the value symbol true (SUBSET-SUM reduction machine)
• Reading a pair bit or vertex mark

Branch after the count comparison (SUBSET-SUM reduction machine) to One halving step of the binary conversion (SUBSET-SUM reduction machine)

• Branch after the count comparison (SUBSET-SUM reduction machine)
• The subset-sum emitter machine
• Start label of the subset-sum emitter
• Testing a popped input bit
• Testing a popped input bit
• Testing a popped input bit
• Subset-sum emitter: reading the unary k
• Subset-sum emitter: unterminated unary prefix at rdK
• Subset-sum emitter: reading the unary n
• Subset-sum emitter: unterminated unary prefix at rdN
• Subset-sum emitter: moving the pair bits
• Run of the pair-counting loop of the subset-sum emitter
• Edge-number phase (SUBSET-SUM reduction machine)
• Subset-sum emitter: one row of the pair walk
• Run of the subset-sum emitter's pair walk
• Subset-sum emitter: one vertex number
• Subset-sum emitter: moving unmarked vertices back to L
• Run of the mark-return loop of the subset-sum emitter
• Run of the vertex-number phase of the subset-sum emitter
• One halving step of the binary conversion (SUBSET-SUM reduction machine)

Binary conversion (SUBSET-SUM reduction machine) to Statements of the SUBSET-SUM verifier

• Binary conversion (SUBSET-SUM reduction machine)
• Run of the target-bit loop of the subset-sum emitter
• Run of the target-output phase of the subset-sum emitter
• Run of the VERTEX-COVER to SUBSET-SUM machine
• Whether a bit string ends in false
• Canonical binary strings are those not ending in zero
• Parsing number blocks, with fuel
• Decoding a SUBSET-SUM instance
• Decoding a SUBSET-SUM instance inverts its encoding
• Numbers chosen by a mask
• The SUBSET-SUM verifier
• Every sublist is selected by a mask
• SUBSET-SUM is characterized by its verifier
• Carry bit of a full adder
• Adding a carry bit
• Ripple-carry addition of bit lists
• Addition is correct on canonical numbers
• Stacks of the SUBSET-SUM verifier
• Labels of the SUBSET-SUM verifier
• Statements of the SUBSET-SUM verifier

Reading one pair of a block to Comparing the sum with the target

• Reading one pair of a block
• Adding one payload bit to the sum
• Carry step of the SUBSET-SUM verifier
• Starting the next number
• The SUBSET-SUM verifier program
• Start state of the SUBSET-SUM verifier
• Stack contents of the SUBSET-SUM verifier
• Rejection by the SUBSET-SUM verifier within a step bound
• Rejecting in one step
• Reading the target block
• Skipping a number block
• Carry phase of the SUBSET-SUM verifier
• Adding a canonical chosen block
• The verifier rejects a chosen block that ends in false
• The verifier rejects an unterminated target block
• The verifier rejects an unterminated skipped block
• The verifier rejects an unterminated chosen block
• Moving the new sum back
• Moving the final sum for the comparison
• Comparing the sum with the target

The summing loop of the SUBSET-SUM verifier to Binary addition of framed numbers in quadratic time

• The summing loop of the SUBSET-SUM verifier
• Cubic bound on the verifier's phase costs
• The SUBSET-SUM verifier machine
• The SUBSET-SUM verifier machine as a host component
• SUBSET-SUM is in NP
• The VERTEX-COVER to SUBSET-SUM machine as a host component
• The VERTEX-COVER to SUBSET-SUM reduction is polynomial-time
• SUBSET-SUM is NP-hard
• SUBSET-SUM is NP-complete
• SUBSET-SUM verifier computes the mask-selected sum
• A long enough all-true mask selects the whole list
• Embedded SUBSET-SUM summing component reaches the mapped label
• Framed input of two natural numbers
• Labels of the binary addition machine
• Identity embedding of the verifier stacks
• Redirection of the verifier's halt labels
• Only halt labels are redirected to the cleanup label
• Binary addition program built on the SUBSET-SUM machine
• Bit length of the sum is at most the input length
• Binary addition of framed numbers in quadratic time

Part 7 of 7

• Embedded run of the binary addition component

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.