Is TSP a more detailed form of the "Set Inclusion" question? Background

Set Inclusion

GIVEN: set of cards, some with blue backs, and each with a positive, integer face value.

QUESTION: Are there any [blue-backed cards] with a [face value &lt;= L]?


2 independent variables: [blue/white cards], [integer face values]


Function A: Select a blue-backed card


face value depends on which card you select
each blue card potentially has face value &lt;= L


thus, worst-case = [check all blue cards]





Function B: Select a face value &lt;= L


blue back depends on which card you select
each card w/ face value &lt;= L potentially has blue back 


thus, worst-case = [check all cards w/ face value &lt;= L]





Function B cannot exist. There is no way to verify that a selected card has a blue back, since don't know key info:


How are cards marked with a blue back?


WORST-CASE: turn over all blue-backed cards (Function A)



Travelling Salesman

GIVEN: complete graph, G(V,E), where all edges are positive, integer values.

DEFINITION: "config"


{A, B, u, v} where u &amp; v are 2 vertices, and A &amp; B are the remaining vertices split up as evenly as possible


DEFINITION: "optimal tour of a config"


shortest path from u to v, only going thru each vertex in A once, and
shortest path from v to u, only going thru each vertex in B once


Assume we have a function, f, that returns the optimal tour for a given config, in sub-exponential time. (EDIT: if you can prove this function must take exponential time, you've shown $P\neq NP$.)

A smallest tour must be the optimal tour of one of the configs in G.
Any config could produce the smallest tour.

NOTE: Each tour is an edge-set that can form |V|/2 or |V| configs, for even or odd |V|, respectively.



A COMPLETE GRAPH is equivalent to: set of cards, some with blue backs, and each with a positive, integer face value.


each card represents a set of edges with size = |V|
blue backs mark any edge-sets that are an optimal tour for a config
face value is the sum of the edge-set represented by the card


QUESTION: Are there any [blue-backed cards] with a [face value &lt;= L]?


2 independent variables: [blue/white cards], [integer face values]


Consider case where L = length of smallest tour.


Only need look at blue cards (edge-sets that are an optimal tour for a config)
Only need look at cards w/ face value = L (edge-sets with sum = L)


Function A: Select blue-backed card


face value depends on which card you select
each blue card potentially has face value = L


thus, worst-case = [check all blue cards]





Function B: Select a card with face value = L


blue back depends on which card you select
each card w/ face value = L potentially has blue back


thus, worst-case = [check all cards w/ face value = L]





Unlike "Set Inclusion", now you can verify that a selected card for Function B has a blue back, by running f on the selected card's configs.

However, controlling either variable, [choosing blue card] or [choosing card w/ face value = L], causes the other to be uncontrollable.

WORST-CASE:


FACE-DOWN Approach: turn over all cards with blue back (Function A)
FACE-UP Approach:   turn over all cards with face value = L (Function B)




Question

So the final question: Is TSP-Decision a version of "Set Inclusion" that has enough information to define a Function B?

If so, does this mean that the worst-case running time of TSP-Decision is lower-bounded by the smaller of the 2 domains of Functions A and B?  i.e. min{number of blue cards, number of cards with face value = L} -- still only for the case where L = length of smallest tour.

EDIT: Both those lower-bounds are exponential, so if we can show that TSP-Decision is lower-bounded by them, we've shown that P != NP.
As far as I can see, your model is that the edges of the graph are represented by cards and the edges on the optimal TSP tour are cards with blue backs. You're asking if TSP corresponds to the problem of identifying the cards with the blue backs.  If that is the case, the answer is "yes".

However, there is a huge caveat. In the set inclusion problem, we can tell in constant time if the back of a card is blue: you just turn over that one card and look at it. You assume that we can do the same in TSP: in constant time, we can tell whether any single edge is in the optimal tour. This is a completely unrealistic assumption because it's impossible to tell if an edge is on the optimal tour without examining at least one edge from every vertex.

I think that what you've observed is basically that, if somebody has somehow solved a TSP instance, you can find the solution by asking them whether each individual edge is in the optimal tour. This is obviously true, but it's not very interesting.