Let $ G (V, E) $ to be a graph.

Let $ S $ either all of the combinations of $ | V | $ edges.

Let $ A $ And $ B $ to be two subsets of $ S $, or:

- each subset is a collection of all the elements of $ S $ who share a common "global property"
- the overall properties of $ A $ And $ B $ are different
- $ | A | gt 0 $
- $ | B | gt 0 $
- $ | A cap B | geq 0 $
- $ A not subseteq B $
- $ B not subseteq A $

**DEFINITION**: Aggregate Property, $ P $of $ Q in S $

Given some $ Q in S $, we must examine each element of $ Q $ in order to check the property $ P $.

- Example for $ Q in A $:[sommedesarêtesdans[sumofedgesin[sommedesarêtesdans[sumofedgesin$ Q $] $ leq $ 40
- Example for $ Q $ B $:[bordsdans[edgesin[bordsdans[edgesin$ Q $ Hamiltonian Cycle form in $ G $]

Let $ alpha $ to be an algorithm that returns an element $ A $given $ G $.

Let $ beta $ to be an algorithm that returns an element $ B $given $ G $.

Each point represents an edge of the graph $ G $:

As a reminder, the global properties of A and B are not the same, therefore:

Key idea 1: Any algorithm that starts at level 1 and ends at level 2 and produces a set of edges with a unique relationship, A, must be an algorithm for α and NOT β.

Let $ gamma $ or any algorithm that returns a set of edges having both the properties A and B, and which does not provide one before the other (does not go to level 3, as described below).

By definition, $ gamma $ is an algorithm for $ alpha $.

By definition, $ gamma $ is an algorithm for $ beta $.

So $ alpha $ and $ beta $ can be equal.

Since $ alpha $ and $ beta $ can be equal, A and B are no longer distinct, because they can be insured using the same algorithm, $ gamma $.

So, A and B are actually the same property.

Key idea 2If an algorithm, γ, which starts at level 1 and ends at level 2, produces a set of edges with 2 relations, M and N, then M and N must be identical.

In order to guarantee 2 distinct properties, $ gamma $ must go to a 3rd level:

So now, $ gamma $ has 2 options:

- Carry out $ alpha $then run $ beta $ (worst case = $ | A | $, must search for the output of $ alpha $ who has $ B $-Property)
- Carry out $ beta $then run $ alpha $ (worst case = $ | B | $, must search for the output of $ beta $ who has $ A $-Property)

Given the context above, *is the time complexity of any algorithm $ gamma $ (the one that produces a set of edges at the intersection of $ A $ and $ B $, so this product set will have 2 aggregate properties) delimited by the top $ | A | $ or $ | B | $?*

If so, and we demonstrate a $ A $ and $ B $ with exponential sizes compared to the input graph, could we use this technique to show that $ gamma $ Should it take an exponential time in the worst case?

This model does not apply to k-SAT because a solution to k-SAT must have only one aggregate property:

**truth values make a true proposition**

Whereas a solution for TSP must have 2 aggregate properties:

**sum of edges $ leq L $****the edges form the Hamiltonian cycle in $ G $**