Hypothetically, I want to construct a graph with certain nodes that I want to hit, then generate a path to hit every node (i.e. travelling salesman). It's NP-Hard to generate a path given a graph, but is it NP-Hard to generate an optimal path and graph in tandem?
In this scenario, I'm restricting the resulting graph so that solving it is NP-Hard. This makes the path valuable/hard to obtain otherwise.
I'm trying to get at a concept similar to factoring large numbers, but prime factors are swapped for the path and the product is swapped for the graph. In theory, you could generate a path/graph pair and keep the path as a secret that proves you generated the public graph. Ideally, it would be easy to make a path and corresponding graph, but nearly impossible to calculate the path given a graph.
Does anyone know if this problem is possible, and if so, any way to approach it? Thanks!
There are several ideas in theoretical computer science that are similar to what you are asking for. Let me try to explain them as well as I am able to.
One-Way Functions
There is something in cryptography called a one-way function. This is a function $f\colon \{0,1\}^* \to \{0,1\}^*$ which is computable in polynomial time but which cannot be inverted in polynomial time even in the average case. Specifically, for every polynomial time algorithm $A$, if you sample a string uniformly at random from $\{0,1\}^n$ then the probability that $f(A(f(x))) = f(x)$ is small (at least for large enough $n$).
Suppose $f$ is a one-way function. Then the following problem is not solvable in polynomial time: given strings $x$ and $y$, is $x$ the initial segment of a string $z$ such that $f(z) = y$? Since $f$ is computable in polynomial time, this problem is clearly in NP. Let's call this problem $f-\mathsf{INVERSION}$.
The point is that $f$ gives us a way to efficiently generate problems and solutions so that with high probability the problem is hard to solve. By passing through the reduction from $f-\mathsf{INVERSION}$ to $\mathsf{TRAVELING-SALESMAN}$ (or whatever), we should get a way to efficiently generate instances of $\mathsf{TRAVELING-SALESMAN}$ with solutions but whose solutions are usually hard to find if you don't already know them. But there's a couple wrinkles.
Hard Core Bits
The first wrinkle is that it's not exactly clear that $f-\mathsf{INVERSION}$ as I've defined it is actually hard on average. It is clear that it's not solvable in polynomial time as long as the original $f$ was really a one way function, but maybe it's only occasionally hard to solve. Fortunately there is a modification of $f-\mathsf{INVERSION}$ that will work.
A hard-core bit of an injective one-way function $f$ is a polynomial time computable function $B\colon \{0,1\}^*\to\{0,1\}$ such that no polynomial time algorithm can guess $B(x)$ from $f(x)$ for more than a small fraction of $x$'s. Goldreich and Levin showed in the 80's that if there is an injective one-way function then there is an injective one-way function with a hard-core bit.
This hard-core bit gives us the desired NP problem for which it is easy to generate hard instances with known solutions. And it is easy to check that if $f$ and $B$ are both computable in polynomial time and $f$ is injective then the following problem is in NP: given a string $y$, is there an $x$ such that $f(x) = y$ and $B(x) = 0$? And the hard-coreness of the hard-core bit $B$ ensures it is easy to generate hard instances of this problem. Let's refer to this problem as $\mathsf{GUESS}(f, B)$
Reducing to Traveling Salesman
So we have our injective one-way function $f$ with hard-core bit $B$. How do we get hard instances of $\mathsf{TRAVELING-SALESMAN}$? Here's the idea. We decide on an input size and choose some appropriate $n$. Then we randomly sample a string $x$ from $\{0,1\}^n$. We compute $f(x)$ to get an instance of $\mathsf{GUESS}(f, B)$. The reduction from $\mathsf{GUESS}(f, B)$ to $\mathsf{TRAVELING-SALESMAN}$ gives us a graph, let's call it $G_x$.
At this point it may not be obvious how to find a solution to the problem $G_x$. But the fact is that the reduction from an arbitrary NP problem to $\mathsf{TRAVELING-SALESMAN}$ has the following property: there is an efficient algorithm to convert a solution to the original problem into a solution to the Traveling Salesman instance and vice-versa. Since we picked $x$ we know a solution to our original problem. So we can easily find a solution to the problem $G_x$.
Likewise, an efficient way to find solutions to the instances of $\mathsf{TRAVELING-SALESMAN}$ that we produce would give us a way to reliably compute the hard-core bit $B$, which is impossible.
Cryptographic Assumptions
Do one-way functions exist? Of course, since their existence implies that P is not equal to NP, they have not been proven to exist. But actually their existence is not even known to follow from the assumption that P is not equal to NP. On the other hand, almost all cryptographers operate under the assumption that one-way functions exist. Also it is worth pointing out here that the usual assumption about one-way functions is that they cannot be inverted in polynomial time, not that inverting them is NP-complete (although I know of no reason for not making the stronger assumption other than that it is not needed for anything in cryptography).
Factoring
The situation with generating hard instances of factoring is a bit different. Factoring is not known (or believed by most people) to be NP-complete. So we cannot just take a one-way function and pass through the reduction to Factoring like we did for Traveling Salesman. On the other hand, one of the few proposed one-way functions is based on factoring, so the cryptography community already apparently believes it is possible to efficiently generate hard instances of Factoring.
Planted Clique Problems
There is also a lot of work outside of cryptography on so-called "Planted Clique" problems. The idea here is to start with a clique of some size and then add a random graph around it. Finding a maximal clique in the resulting graph is conjectured to be impossible to do in polynomial time in the average case. And if that conjecture is correct it would give another route to answering your questions. As with one-way functions, this conjecture is not known to follow only from the assumption that P is not equal to NP. I also don't know much about this topic.