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)
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$