1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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 ? $\endgroup$ – Vince Jan 17 at 9:38
  • $\begingroup$ 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? $\endgroup$ – dkaeae Jan 17 at 10:47
  • $\begingroup$ 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 $\endgroup$ – Alberto Romañach Jan 17 at 11:04
  • $\begingroup$ 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 $\endgroup$ – Alberto Romañach Jan 17 at 11:14
  • $\begingroup$ 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.... $\endgroup$ – Vince Jan 17 at 12:44
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you misunderstand the model. $\endgroup$ – Alberto Romañach Jan 17 at 10:42
  • $\begingroup$ Each card represents a set of edges, of size equal to the number of vertices. $\endgroup$ – Alberto Romañach Jan 17 at 10:43
  • $\begingroup$ Then I have exponentially many cards, which is a bad start. And I still need to tell in constant time whether any individual card represents the optimal solution, which is still unrealistic. $\endgroup$ – David Richerby Jan 17 at 10:44
  • $\begingroup$ Sure it might be unrealistic, but that's not the point I'm trying to convey. Can we simply assume that such a function exists? $\endgroup$ – Alberto Romañach Jan 17 at 10:50
  • $\begingroup$ And to clarify, we only need to tell in constant time whether a card represents a potentially optimal solution, i.e. any set that is the "optimal tour for a config," as previously defined. $\endgroup$ – Alberto Romañach Jan 17 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.