*Background*

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

Let $ S$ be the set of all combinations of $ |V|$ edges.

Let $ A$ & $ B$ be two subsets of $ S$ , where:

- each subset is a collection of all elements of $ S$ that share a common “aggregate property”
- the aggregate properties of $ A$ & $ 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$ , one must examine every element in $ Q$ in order to verify property $ P$ .

- Example for $ Q \in A$ : [sum of edges in $ Q$ ] $ \leq 40$
- Example for $ Q \in B$ : [edges in $ Q$ form Hamiltonian Cycle in $ G$ ]

Let $ \alpha$ be any algorithm that returns an element in $ A$ , given $ G$ .

Let $ \beta$ be any algorithm that returns an element in $ B$ , given $ G$ .

Each dot represents an edge in the graph $ G$ :

Reminder, the aggregate properties of A and B are not the same, thus:

**Key Idea 1**: Any algorithm which 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$ be any algorithm that returns a set of edges with both properties A and B, and which doesn’t ensure 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$ .

Thus $ \alpha$ and $ \beta$ can be equal.

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

Thus A and B are actually the same property.

**Key Idea 2**: If an algorithm, γ, which starts at Level 1 and ends at Level 2, produces a set of edges with 2 relationships, M and N, then M and N must be the same relationship.

In order to ensure 2 distinct properties, $ \gamma$ must go to a 3rd Level:

So now, $ \gamma$ has 2 options:

- Perform $ \alpha$ , then run $ \beta$ (worst-case = $ |A|$ , must search for output of $ \alpha$ that has $ B$ -Property)
- Perform $ \beta$ , then run $ \alpha$ (worst-case = $ |B|$ , must search for output of $ \beta$ that has $ A$ -Property)

*Question*

Given the above background, *is the time-complexity of any algorithm $ \gamma$ (one that produces a set of edges in the intersection of $ A$ and $ B$ , so that this produced set will have 2 aggregate properties) upper-bounded by $ |A|$ or $ |B|$ ?*

If yes, and we demonstrate an $ A$ and $ B$ with exponential sizes in relation to the input graph, could we use this technique to show that $ \gamma$ MUST take exponential time in the worst-case?

*Note Regarding k-SAT*

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

**truth values make a proposition True**

Whereas a solution for TSP must have 2 aggregate properties:

**sum of edges $ \leq L$ **
**edges form Hamiltonian Cycle in $ G$ **