# 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 <= 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 <= L
• thus, worst-case = [check all blue cards]

Function B: Select a 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]

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 & v are 2 vertices, and A & 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 <= 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.

• How can people understand your issue if you put a hard mixutre of the initial problem, TSP explanation, your reasoning.... Just detail correctly the PROBLEM ! Why cannot you just loop on all cards and check which is blue and have good value ? – Optidad Jan 17 '19 at 9:38
• Adding to Vince's comment, it would be helpful to know what your motivation is (even if just a single sentence of it). Just why should this particular problem be considered interesting? – dkaeae Jan 17 '19 at 10:47
• Apologies if my post was confusing. I was outlining some background first, then towards the end I stated my question. Here was the thought behind the format: Part 1 - Set Inclusion: a simple problem that was related to TSP Part 2 - TSP: showing how TSP is similar to "Set Inclusion" Part 3 - Question: the final question restated – Alberto Romañach Jan 17 '19 at 11:04
• And for @dkaeae , if TSP-Decision turns out to be like "Set Inclusion," we'll be able to show that any exact algorithm for TSP-Decision must run in exponential time in the worst-case, which would imply P != NP – Alberto Romañach Jan 17 '19 at 11:14
• So you run TSP to build every combinatoric possible and mark the good one in blue. Then you loop on all the combinatoric and check if it is blue to get the best function to solve TSP... I think you indeed proved than NP=NP and that even on a NP algorithm, it s possible to waste lot of ressource.... – Optidad Jan 17 '19 at 12:44