<p>We answer OP's question in the negative.
These results are for OP's problem
with the monotonicity requirements on <span class="math-container">$f$</span>
(added in OP's edit after @Tassle's answer, invalidating that answer).</p>
<p><strong>Lemma 1.</strong> <em>This problem:</em></p>
<ol>
<li><p><em>has worst-case query complexity (deterministic and Las-Vegas randomized) <span class="math-container">$n 2^{n-1}$</span>,</em></p>
</li>
<li><p><em>has an <span class="math-container">$O(n 2^n)$</span>-time deterministic algorithm, and</em></p>
</li>
<li><p><em>is <s>strongly</s> NP-hard.</em></p>
</li>
</ol>
<p><em>[Edit: strong NP-hardness depends on the encoding.
See remarks at the end.]</em></p>
<hr />
<p><em>Proof.</em></p>
<h5>Lower bound on query complexity</h5>
<p>Fix <span class="math-container">$n$</span> and let <span class="math-container">$I'$</span> be the instance of OP's problem defined by
<span class="math-container">$$f(L, i) = L + 2^{i-1}.$$</span>
For this instance, every permutation has the same cost,
namely <span class="math-container">$\sum_{i=1}^{n} 2^{i-1} = 2^n-1$</span>.</p>
<p>Let <span class="math-container">$B_b(q)$</span> denote the <span class="math-container">$b$</span>th bit in the binary representation
of <span class="math-container">$q\in \mathbb N$</span>.
Let
<span class="math-container">$$X = \{(q, b) \in \mathbb N \times [n] : q \le 2^n-1
\textsf{ and } B_b(q) = 0\}.$$</span></p>
<p>For any <span class="math-container">$(q, b)\in X$</span>,
let <span class="math-container">$I(q,b)$</span> denote the instance of OP's problem
defined by <span class="math-container">$$f(L, i) = \begin{cases}
L + 2^{i-1} - 1&amp; ~(L, i) = (q, b) \\
L + 2^{i-1} &amp;~\textit{otherwise}.
\end{cases}$$</span>
Note that there is a permutation with cost
<span class="math-container">$-1 + \sum_{i=1}^n 2^{i-1} = 2^n-2$</span>,
namely, take first the indices that are 1 in the binary representation of <span class="math-container">$q$</span>,
then take index <span class="math-container">$b$</span>,
then take the remaining indices.</p>
<p>Fix any algorithm (deterministic or randomized)
that is guaranteed to give a correct answer.
Simulate the algorithm on the first instance <span class="math-container">$I'$</span> above.
If, for some <span class="math-container">$(q, b)\in X$</span>,
the algorithm doesn't query <span class="math-container">$f(q, b)$</span>,
then it can't distinguish between <span class="math-container">$I'$</span> and <span class="math-container">$I(q, b)$</span>,
so must give the wrong answer
on one of those two instances
(with positive probability).
This cannot be, as the algorithm is guaranteed to give a correct answer.
Hence, the algorithm must make at least <span class="math-container">$|X|$</span> queries.</p>
<p>To calculate <span class="math-container">$|X|$</span>,
associate with each <span class="math-container">$q$</span>
the set <span class="math-container">$S(q)\subseteq [n]$</span> of indices of zero-bits in <span class="math-container">$q$</span>,
so <span class="math-container">$(q, b) \in X$</span> iff <span class="math-container">$b\in S(q)$</span>.
Then <span class="math-container">$|X| = \sum_{q=0}^{2^{n-1}} |S(q)|
= \sum_{S\subseteq [n]} |S| = n 2^{n-1}$</span>.</p>
<hr />
<h4>Upper bound on query complexity and run time</h4>
<p>Consider the following dynamic-programming algorithm.
For every subset <span class="math-container">$S\subseteq [n]$</span>, define
<span class="math-container">$M(S)$</span> to be the minimum cost of any permutation of the indices in <span class="math-container">$S$</span>.
The following recurrence holds:
<span class="math-container">$$M(S) = \begin{cases}
0 &amp; ~(S=\emptyset) \\
\min_{i\in S} f\big(M(S\setminus\{i\}), i\big) &amp; ~(S\ne \emptyset).
\end{cases}$$</span>
The recurrence holds because of the second monotonicity requirement,
that is, <span class="math-container">$L \mapsto f(L, i)$</span> is non-decreasing for any fixed <span class="math-container">$i$</span>.
(Because of this property,
in any minimum cost permutation <span class="math-container">$(\pi_1, \pi_2, \ldots, \pi_n)$</span> of <span class="math-container">$[n]$</span>,
any prefix <span class="math-container">$(\pi_1, \pi_2, \ldots, \pi_k)$</span>
can be replaced by the reordering of the prefix
that gives minimum cost <span class="math-container">$M(\{\pi_1, \pi_2, \ldots, \pi_k\})$</span>,
without increasing the cost of <span class="math-container">$\pi$</span>.)</p>
<p>The query complexity is <span class="math-container">$\sum_{S\subseteq [n]} |S| = n 2^{n-1}$</span>.
The running time is proportional to this.</p>
<hr />
<h4>Strong (?) NP-hardness</h4>
<p>The proof, by reduction from <a href="https://en.wikipedia.org/wiki/Partition_problem#Variants_and_generalizations" rel="nofollow noreferrer">Product Partition</a>, is similar in spirit to @Tassle's.  Given an instance <span class="math-container">$W=(w_1, w_2, \ldots, w_m)\in\mathbb N^m$</span> of Product Partition, let <span class="math-container">$T(W)=\sqrt{\prod_{i=1}^m w_i} \in\mathbb N$</span>.  Given <span class="math-container">$W$</span>, the reduction constructs the instance of OP's problem, with <span class="math-container">$n=m+1$</span>, defined by
<span class="math-container">$$f(L, i) = \begin{cases}
L \times w_i &amp; ~(i \le m) \\
L &amp; ~(i = m+1 \textsf{ and } L = T(W) \\
L + 1 &amp; ~(i = m+1 \textsf{ and } L \ne T(W).
\end{cases}$$</span>
Suppose there is <span class="math-container">$S\subseteq [m]$</span> with <span class="math-container">$\prod_{i\in S} w_i = T(W)$</span>.
Then there is a solution to this instance of OP's problem
that has cost <span class="math-container">$T(W)^2$</span>.
(Take any permutation of <span class="math-container">$S$</span>, followed by <span class="math-container">$i=m+1$</span>, followed by any permutation of <span class="math-container">$\overline S$</span>.)</p>
<p>Conversely, given any permutation that achieves cost <span class="math-container">$T(W)^2$</span>,
it must be that index <span class="math-container">$m+1$</span> contributes nothing additional
to the cost, that is, the cost <span class="math-container">$L$</span> just before index <span class="math-container">$m+1$</span>
must satisfy <span class="math-container">$f(L, m+1) = L$</span>.  The only cost that does this is <span class="math-container">$L=T(W)$</span>.
So it must be that the product of the weights of the indices
taken before <span class="math-container">$m+1$</span> is <span class="math-container">$T(W)$</span>.</p>
<p><em>[EDIT 2: As discussed in the comments, this proof assumed <span class="math-container">$L$</span> is initialized to 1, but the problem specifies that <span class="math-container">$L$</span> is initialized to 0.  To patch this, add artificial index <span class="math-container">$m+2$</span>
with <span class="math-container">$f(0, m+2) = 1$</span> and <span class="math-container">$f(L, m+2) = L + T(W)^2$</span> for <span class="math-container">$L&gt;0$</span>.]</em>
<span class="math-container">$~~~\Box$</span></p>
<p>[<em>EDIT 1</em>: Whether this reduction shows <em>strong</em> NP-hardness depends on how <span class="math-container">$f$</span>, and the target value (in decision-problem form), are encoded.  Note that the value of <span class="math-container">$T(W)$</span> is not polynomial even when the values of the <span class="math-container">$w_i$</span>'s are, so the standard unary encodings of <span class="math-container">$T(W)$</span> (in <span class="math-container">$f$</span>) and <span class="math-container">$T(W)^2$</span> (in the target value) would be exponentially large.  One can work around this by encoding <span class="math-container">$f$</span> and <span class="math-container">$T(W)^2$</span> differently, namely, replacing the condition <span class="math-container">$L=T(W)$</span> by <span class="math-container">$\prod_{i: B_i(L)=0} w_i = \prod_{i: B_i(L)=1} w_i$</span>, and encoding <span class="math-container">$T(W)^2$</span> implicitly by giving the <span class="math-container">$w_i$</span>'s in unary.
In short, when defining &quot;strongly&quot; NP-complete for OP's problem, it's not clear how the encoding of <span class="math-container">$f$</span> (which is not a number) should be considered, but, it seems that there is at least a <em>restriction</em> of OP's problem that, with suitable encoding, is strongly NP-complete.  See <a href="https://cstheory.stackexchange.com/questions/16902/subset-sum-vs-subset-product-strong-vs-weak-np-hardness#comment120024_16902">here</a>
for related discussion.]</p>
<hr />

CC BY-SA 4.0
2024-03-11T14:24:12.070Z
Regarding the hardness proof: if $f(L,i) = w_i  \cdot L$, and $L$ starts at $0$, don't we remain "stuck" at 0?
Erel Segal-Halevi
CC BY-SA 4.0
2024-03-11T15:53:34.600Z
Whoops, yes, that's a mistake in the proof.  You need a gadget that forces an artificial "start" at L = 1.  E.g. add another artificial element $m+2$ and define $f(0, m+2) = 1$, and $f(L, m+2) = L + T(W)^2$ for $L > 0$.  (This gadget interferes a little with _strong_ NP-hardness, similar to the comment in the EDIT.)
Neal Young
CC BY-SA 4.0
2024-03-11T18:27:18.000Z
The definition $f(L,m+1)=L$ does not match the requirement that $f(L,i)>L$. Can it be amended?
Erel Segal-Halevi
CC BY-SA 4.0
2024-03-11T18:45:17.293Z
Whoops, I thought the requirement was $f(L, i) \ge L$.  Yes, this can be fixed.  E.g. redefine $f(L, m+1)$ to be $2L$ if $L=T(W)$ and otherwise $3L$, then adjust the target accordingly.  Do you similarly care that the definitions yield $f(0, i) = 0$ in some cases?  If so, with the fix in the previous comment, you can just take, say, $f(L, i) = 1$ for $L < 1$ and $i\le m+1$.
Neal Young
CC BY-SA 4.0
2024-02-17T21:06:34.950Z
2024-03-11T15:57:57.137Z
2024-03-11T15:57:57.137Z
Neal Young
<p>Without the monotonicity condition, if <span class="math-container">$f$</span> is given only by oracle access, then in the worst case you need to query it <span class="math-container">$\Omega(n!)$</span> times.</p>
<p>Proof sketch:</p>
<p>For some sequence of integers <span class="math-container">$S=[a_1, a_2, \ldots a_k]$</span> (where <span class="math-container">$1\leq a_i \leq n$</span> for all <span class="math-container">$i$</span>), let <span class="math-container">$E_S$</span> be some encoding of <span class="math-container">$S$</span> as a positive integer (you can easily encode <span class="math-container">$S$</span> with <span class="math-container">$O(k\log n)$</span> bits).</p>
<p>Fix some specific (but unknown) permutation <span class="math-container">$P = [p_1, p_2, \ldots, p_n]$</span> and consider the following function <span class="math-container">$f$</span>:</p>
<ul>
<li>it maps <span class="math-container">$(0, x)$</span> to <span class="math-container">$E_{[x]}$</span>;</li>
<li>it maps <span class="math-container">$(E_{[a_1, a_2, \ldots a_k]}, x)$</span> to <span class="math-container">$E_{[a_1, a_2, \ldots a_k, x]}$</span> if <span class="math-container">$[a_1, a_2, \ldots a_k, x] \neq P$</span>;</li>
<li>it maps <span class="math-container">$(E_{[a_1, a_2, \ldots a_k]}, x)$</span> to <span class="math-container">$0$</span> if <span class="math-container">$[a_1, a_2, \ldots a_k, x] = P$</span>;</li>
<li>it maps anything else to whatever.</li>
</ul>
<p>The length of <span class="math-container">$P$</span> is <span class="math-container">$0$</span>, while the length of any other permutation is <span class="math-container">$&gt;0$</span>. The only way to find out <span class="math-container">$P$</span> is by testing it, and testing any other permutation gives you no information except that it isn't <span class="math-container">$P$</span>. Thus, there is no better strategy than to bruteforce every permutation until finding <span class="math-container">$P$</span>.</p>
<hr />
<p>Even if <span class="math-container">$f$</span> is not given in a black box manner, the problem is still <span class="math-container">$\textrm{NP}$</span>-hard.</p>
<p>You can show this by reducing from the partition problem. Consider an instance <span class="math-container">$S=[a_1, a_2, \ldots a_n]$</span>,  of the partition problem, with <span class="math-container">$a_1+ a_2 + \ldots + a_n = 2N$</span>.</p>
<p>Let <span class="math-container">$f$</span> defined as follows:</p>
<ul>
<li>it maps <span class="math-container">$L,x$</span> to <span class="math-container">$L+a_x$</span> if <span class="math-container">$L\neq N$</span>;</li>
<li>it maps <span class="math-container">$N,x$</span> to <span class="math-container">$N$</span>.</li>
</ul>
<p>Then it is easy to see that there is a partition of <span class="math-container">$S$</span> into two subsets of weight <span class="math-container">$N$</span> if and only if the permutation with minimum weight has weight <span class="math-container">$N$</span>.</p>
<hr />
<p>EDIT: inspired by Neal Young's answer, the above reduction can be amended to satisfy the monotonicity condition. Given an instance of Partition with <span class="math-container">$m$</span> integers <span class="math-container">$a_1,\ldots,a_m$</span>, define an instance of the OP problem with <span class="math-container">$n=m+1$</span> by:</p>
<ul>
<li><span class="math-container">$f(L,i) = L+a_i$</span> for all <span class="math-container">$i\in \{1,\ldots,m\}$</span>;</li>
<li><span class="math-container">$f(L,m+1) = L+2$</span> for <span class="math-container">$L\neq N$</span>;</li>
<li><span class="math-container">$f(N,m+1) = N+1$</span>.</li>
</ul>
<p>If the Partition instance admits an equal partition, then the optimal cost is <span class="math-container">$2N+1$</span>: the permutation starts with one subset of sum <span class="math-container">$N$</span>, then <span class="math-container">$m+1$</span>, then the other subset of sum <span class="math-container">$N$</span>.
If the Partition instance does not admit an equal partition, then the cost is <span class="math-container">$2N+2$</span> for any permutation.</p>

CC BY-SA 4.0
2024-02-11T13:59:07.513Z
Thanks! But there are important conditions on $f$ that, unfortunately, I forgot to mention: the function $f(L,x)$ should satisfy $f(L,x)\geq L$ for all $x$ (as the length of a path only increases). Moreover, $f(L,x)$ should be a weakly monotonically increasing function of $L$ for all $x$, due to the same reason.
Erel Segal-Halevi
CC BY-SA 4.0
2024-02-11T15:45:00.910Z
@ErelSegal-Halevi I'm pretty sure we can modify my constructions to obey these conditions without too much trouble. I'll edit when I get some time.
Tassle
CC BY-SA 4.0
2024-02-12T12:45:14.033Z
@ErelSegal-Halevi I'm actually having a bit of trouble with the second condition, but I don't see the motivation for introducing it. It doesn't hold in the usual setting. You could have a short initial path with a big jump to reach $x$, while a longer initial path would have made that final step small enough to compensate.
Tassle
CC BY-SA 4.0
2024-02-13T19:19:42.203Z
In my application, all paths with the same length L essentially end in the same point (this is why the next leg only depends on L and on i). Does this monotonicity condition make the problem polynomial-time?
Erel Segal-Halevi
CC BY-SA 4.0
2024-02-11T13:27:04.487Z
2024-03-11T18:32:20.200Z
2024-03-11T18:32:20.200Z
Tassle
<p>The similarity to Travelling Salesman confused me: the more relevant problem is <a href="https://en.wikipedia.org/wiki/Single-machine_scheduling#fatigue" rel="nofollow noreferrer">single-machine scheduling with non-constant job lengths</a>. In particular, <a href="https://www.sciencedirect.com/science/article/pii/S0377221702009098" rel="nofollow noreferrer">this paper</a> surveys many scheduling problems in which the job length depends on the time in which it starts. The most relevant one seems to be <a href="https://onlinelibrary.wiley.com/doi/abs/10.1002/(SICI)1520-6750(199808)45:5%3C511::AID-NAV5%3E3.0.CO;2-6" rel="nofollow noreferrer">this paper</a>. In their model, the length of job <span class="math-container">$j$</span> is <span class="math-container">$p_j$</span> if it starts before some due-date <span class="math-container">$d$</span>, and <span class="math-container">$p_j+b_j*(s_j-d)$</span> if it starts at time <span class="math-container">$s_j &gt; d$</span>. In our notation, this can be written as:</p>
<p><span class="math-container">$$
f(L,i) = L + p_i \text{  if $L\leq d$}
$$</span></p>
<p><span class="math-container">$$
f(L,i) = L + p_i + b_i\cdot (L-d)  \text{  if $L&gt; d$}
$$</span></p>
<p>It satisfies both conditions, and the authors prove that the problem is NP-hard.</p>

CC BY-SA 4.0
2024-02-17T21:05:28.353Z
2024-02-27T19:07:07.583Z
2024-02-27T19:07:07.583Z
Erel Segal-Halevi
<p>The <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">travelling salesman problem</a> can be seen as a problem of selecting a permutation on <span class="math-container">$\{1,\ldots,n\}$</span> of minimun length, where the length of a permutation <span class="math-container">$\sigma$</span> is determined by pairwise distances between adjacent elements, i.e., <span class="math-container">$L(\sigma) := \sum_{i=1}^n d(\sigma(i), \sigma(i-1))$</span>, where <span class="math-container">$d$</span> is a function given as an input, <span class="math-container">$d: [n]\times[n]\to \mathbb{R}_+$</span>.</p>
<p>I am interested in a variant in which the length of <span class="math-container">$\sigma$</span> is determined by the following algorithm:</p>
<ol>
<li><p>Initialize <span class="math-container">$L := 0$</span>;</p>
</li>
<li><p>For <span class="math-container">$i := 1,\ldots,n$</span>:</p>
<ul>
<li>Set <span class="math-container">$L := f(L, \sigma(i))$</span>,</li>
</ul>
</li>
</ol>
<p>where <span class="math-container">$f: \mathbb{R}_+\times [n] \to \mathbb{R}_+$</span> is a function given as an input. In other words, the distance needed to reach the next node depends both on the node and on the total distance travelled so far (but not on the previous node).
The computational model is Real RAM, and <span class="math-container">$f$</span> is given by an oracle access.</p>
<p>Can this variant be solved using poly(<span class="math-container">$n$</span>) calls to <span class="math-container">$f$</span>?</p>
<p>EDIT: As the function <span class="math-container">$f$</span> represents increasing length, it should satisfy the following conditions:</p>
<ul>
<li><span class="math-container">$f(L,i) &gt; L$</span> for all <span class="math-container">$i, L$</span> (as the length of a path only increases).</li>
<li><span class="math-container">$f(L,i)$</span> is a weakly monotonically increasing function of <span class="math-container">$L$</span> for all <span class="math-container">$i$</span>.</li>
</ul>
<p>Sorry for the omission.</p>

CC BY-SA 4.0
2024-02-11T08:51:11.257Z
Are you interested only in the number of calls to $f$? Not in runtime?
Tassle
CC BY-SA 4.0
2024-02-11T11:56:18.580Z
@Tassle yes, this is my primary interest (of course, any other information on this problem would be interesting too).
Erel Segal-Halevi
<np-hardness><tsp>
A Travelling Salesman variant where the next distance depends on distance travelled so far
Erel Segal-Halevi
# A Travelling Salesman variant where the next distance depends on distance travelled so far

(Asked by: username_0 on 2024-02-10)

The [travelling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) can be seen as a problem of selecting a permutation on $\{1,\ldots,n\}$ of minimun length, where the length of a permutation $\sigma$ is determined by pairwise distances between adjacent elements, i.e., $L(\sigma) := \sum\_{i=1}^n d(\sigma(i), \sigma(i-1))$, where $d$ is a function given as an input, $d: [n]\times[n]\to \mathbb{R}\_+$.

I am interested in a variant in which the length of $\sigma$ is determined by the following algorithm:

1. Initialize $L := 0$;
2. For $i := 1,\ldots,n$:

   * Set $L := f(L, \sigma(i))$,

where $f: \mathbb{R}\_+\times [n] \to \mathbb{R}\_+$ is a function given as an input. In other words, the distance needed to reach the next node depends both on the node and on the total distance travelled so far (but not on the previous node).
The computational model is Real RAM, and $f$ is given by an oracle access.

Can this variant be solved using poly($n$) calls to $f$?

EDIT: As the function $f$ represents increasing length, it should satisfy the following conditions:

* $f(L,i) > L$ for all $i, L$ (as the length of a path only increases).
* $f(L,i)$ is a weakly monotonically increasing function of $L$ for all $i$.

Sorry for the omission.

**Tags:** np-hardness, tsp
> **Comments:**
> **username_1**: Are you interested only in the number of calls to $f$? Not in runtime?  
> **username_0**: @Tassle yes, this is my primary interest (of course, any other information on this problem would be interesting too).  

---

## 3 answers

### Answer by username_2 on 2024-02-17. Score: 5 | Accepted answer

We answer OP's question in the negative.
These results are for OP's problem
with the monotonicity requirements on $f$
(added in OP's edit after @Tassle's answer, invalidating that answer).

**Lemma 1.** *This problem:*

1. *has worst-case query complexity (deterministic and Las-Vegas randomized) $n 2^{n-1}$,*
2. *has an $O(n 2^n)$-time deterministic algorithm, and*
3. *is ~~strongly~~ NP-hard.*

*[Edit: strong NP-hardness depends on the encoding.
See remarks at the end.]*

---

*Proof.*

##### Lower bound on query complexity

Fix $n$ and let $I'$ be the instance of OP's problem defined by
$$f(L, i) = L + 2^{i-1}.$$
For this instance, every permutation has the same cost,
namely $\sum\_{i=1}^{n} 2^{i-1} = 2^n-1$.

Let $B\_b(q)$ denote the $b$th bit in the binary representation
of $q\in \mathbb N$.
Let
$$X = \{(q, b) \in \mathbb N \times [n] : q \le 2^n-1
\textsf{ and } B\_b(q) = 0\}.$$

For any $(q, b)\in X$,
let $I(q,b)$ denote the instance of OP's problem
defined by $$f(L, i) = \begin{cases}
L + 2^{i-1} - 1& ~(L, i) = (q, b) \\
L + 2^{i-1} &~\textit{otherwise}.
\end{cases}$$
Note that there is a permutation with cost
$-1 + \sum\_{i=1}^n 2^{i-1} = 2^n-2$,
namely, take first the indices that are 1 in the binary representation of $q$,
then take index $b$,
then take the remaining indices.

Fix any algorithm (deterministic or randomized)
that is guaranteed to give a correct answer.
Simulate the algorithm on the first instance $I'$ above.
If, for some $(q, b)\in X$,
the algorithm doesn't query $f(q, b)$,
then it can't distinguish between $I'$ and $I(q, b)$,
so must give the wrong answer
on one of those two instances
(with positive probability).
This cannot be, as the algorithm is guaranteed to give a correct answer.
Hence, the algorithm must make at least $|X|$ queries.

To calculate $|X|$,
associate with each $q$
the set $S(q)\subseteq [n]$ of indices of zero-bits in $q$,
so $(q, b) \in X$ iff $b\in S(q)$.
Then $|X| = \sum\_{q=0}^{2^{n-1}} |S(q)|
= \sum\_{S\subseteq [n]} |S| = n 2^{n-1}$.

---

#### Upper bound on query complexity and run time

Consider the following dynamic-programming algorithm.
For every subset $S\subseteq [n]$, define
$M(S)$ to be the minimum cost of any permutation of the indices in $S$.
The following recurrence holds:
$$M(S) = \begin{cases}
0 & ~(S=\emptyset) \\
\min\_{i\in S} f\big(M(S\setminus\{i\}), i\big) & ~(S\ne \emptyset).
\end{cases}$$
The recurrence holds because of the second monotonicity requirement,
that is, $L \mapsto f(L, i)$ is non-decreasing for any fixed $i$.
(Because of this property,
in any minimum cost permutation $(\pi\_1, \pi\_2, \ldots, \pi\_n)$ of $[n]$,
any prefix $(\pi\_1, \pi\_2, \ldots, \pi\_k)$
can be replaced by the reordering of the prefix
that gives minimum cost $M(\{\pi\_1, \pi\_2, \ldots, \pi\_k\})$,
without increasing the cost of $\pi$.)

The query complexity is $\sum\_{S\subseteq [n]} |S| = n 2^{n-1}$.
The running time is proportional to this.

---

#### Strong (?) NP-hardness

The proof, by reduction from [Product Partition](https://en.wikipedia.org/wiki/Partition_problem#Variants_and_generalizations), is similar in spirit to @Tassle's. Given an instance $W=(w\_1, w\_2, \ldots, w\_m)\in\mathbb N^m$ of Product Partition, let $T(W)=\sqrt{\prod\_{i=1}^m w\_i} \in\mathbb N$. Given $W$, the reduction constructs the instance of OP's problem, with $n=m+1$, defined by
$$f(L, i) = \begin{cases}
L \times w\_i & ~(i \le m) \\
L & ~(i = m+1 \textsf{ and } L = T(W) \\
L + 1 & ~(i = m+1 \textsf{ and } L \ne T(W).
\end{cases}$$
Suppose there is $S\subseteq [m]$ with $\prod\_{i\in S} w\_i = T(W)$.
Then there is a solution to this instance of OP's problem
that has cost $T(W)^2$.
(Take any permutation of $S$, followed by $i=m+1$, followed by any permutation of $\overline S$.)

Conversely, given any permutation that achieves cost $T(W)^2$,
it must be that index $m+1$ contributes nothing additional
to the cost, that is, the cost $L$ just before index $m+1$
must satisfy $f(L, m+1) = L$. The only cost that does this is $L=T(W)$.
So it must be that the product of the weights of the indices
taken before $m+1$ is $T(W)$.

*[EDIT 2: As discussed in the comments, this proof assumed $L$ is initialized to 1, but the problem specifies that $L$ is initialized to 0. To patch this, add artificial index $m+2$
with $f(0, m+2) = 1$ and $f(L, m+2) = L + T(W)^2$ for $L>0$.]*
$~~~\Box$

[*EDIT 1*: Whether this reduction shows *strong* NP-hardness depends on how $f$, and the target value (in decision-problem form), are encoded. Note that the value of $T(W)$ is not polynomial even when the values of the $w\_i$'s are, so the standard unary encodings of $T(W)$ (in $f$) and $T(W)^2$ (in the target value) would be exponentially large. One can work around this by encoding $f$ and $T(W)^2$ differently, namely, replacing the condition $L=T(W)$ by $\prod\_{i: B\_i(L)=0} w\_i = \prod\_{i: B\_i(L)=1} w\_i$, and encoding $T(W)^2$ implicitly by giving the $w\_i$'s in unary.
In short, when defining "strongly" NP-complete for OP's problem, it's not clear how the encoding of $f$ (which is not a number) should be considered, but, it seems that there is at least a *restriction* of OP's problem that, with suitable encoding, is strongly NP-complete. See [here](https://cstheory.stackexchange.com/questions/16902/subset-sum-vs-subset-product-strong-vs-weak-np-hardness#comment120024_16902)
for related discussion.]

---

> **Comments:**
> **username_0**: Regarding the hardness proof: if $f(L,i) = w_i  \cdot L$, and $L$ starts at $0$, don't we remain "stuck" at 0?  
> **username_2**: Whoops, yes, that's a mistake in the proof.  You need a gadget that forces an artificial "start" at L = 1.  E.g. add another artificial element $m+2$ and define $f(0, m+2) = 1$, and $f(L, m+2) = L + T(W)^2$ for $L > 0$.  (This gadget interferes a little with _strong_ NP-hardness, similar to the comment in the EDIT.)  
> **username_0**: The definition $f(L,m+1)=L$ does not match the requirement that $f(L,i)>L$. Can it be amended?  
> **username_2**: Whoops, I thought the requirement was $f(L, i) \ge L$.  Yes, this can be fixed.  E.g. redefine $f(L, m+1)$ to be $2L$ if $L=T(W)$ and otherwise $3L$, then adjust the target accordingly.  Do you similarly care that the definitions yield $f(0, i) = 0$ in some cases?  If so, with the fix in the previous comment, you can just take, say, $f(L, i) = 1$ for $L < 1$ and $i\le m+1$.  

---

### Answer by username_1 on 2024-02-11. Score: 7

Without the monotonicity condition, if $f$ is given only by oracle access, then in the worst case you need to query it $\Omega(n!)$ times.

Proof sketch:

For some sequence of integers $S=[a\_1, a\_2, \ldots a\_k]$ (where $1\leq a\_i \leq n$ for all $i$), let $E\_S$ be some encoding of $S$ as a positive integer (you can easily encode $S$ with $O(k\log n)$ bits).

Fix some specific (but unknown) permutation $P = [p\_1, p\_2, \ldots, p\_n]$ and consider the following function $f$:

* it maps $(0, x)$ to $E\_{[x]}$;
* it maps $(E\_{[a\_1, a\_2, \ldots a\_k]}, x)$ to $E\_{[a\_1, a\_2, \ldots a\_k, x]}$ if $[a\_1, a\_2, \ldots a\_k, x] \neq P$;
* it maps $(E\_{[a\_1, a\_2, \ldots a\_k]}, x)$ to $0$ if $[a\_1, a\_2, \ldots a\_k, x] = P$;
* it maps anything else to whatever.

The length of $P$ is $0$, while the length of any other permutation is $>0$. The only way to find out $P$ is by testing it, and testing any other permutation gives you no information except that it isn't $P$. Thus, there is no better strategy than to bruteforce every permutation until finding $P$.

---

Even if $f$ is not given in a black box manner, the problem is still $\textrm{NP}$-hard.

You can show this by reducing from the partition problem. Consider an instance $S=[a\_1, a\_2, \ldots a\_n]$, of the partition problem, with $a\_1+ a\_2 + \ldots + a\_n = 2N$.

Let $f$ defined as follows:

* it maps $L,x$ to $L+a\_x$ if $L\neq N$;
* it maps $N,x$ to $N$.

Then it is easy to see that there is a partition of $S$ into two subsets of weight $N$ if and only if the permutation with minimum weight has weight $N$.

---

EDIT: inspired by Neal Young's answer, the above reduction can be amended to satisfy the monotonicity condition. Given an instance of Partition with $m$ integers $a\_1,\ldots,a\_m$, define an instance of the OP problem with $n=m+1$ by:

* $f(L,i) = L+a\_i$ for all $i\in \{1,\ldots,m\}$;
* $f(L,m+1) = L+2$ for $L\neq N$;
* $f(N,m+1) = N+1$.

If the Partition instance admits an equal partition, then the optimal cost is $2N+1$: the permutation starts with one subset of sum $N$, then $m+1$, then the other subset of sum $N$.
If the Partition instance does not admit an equal partition, then the cost is $2N+2$ for any permutation.

> **Comments:**
> **username_0**: Thanks! But there are important conditions on $f$ that, unfortunately, I forgot to mention: the function $f(L,x)$ should satisfy $f(L,x)\geq L$ for all $x$ (as the length of a path only increases). Moreover, $f(L,x)$ should be a weakly monotonically increasing function of $L$ for all $x$, due to the same reason.  
> **username_1**: @ErelSegal-Halevi I'm pretty sure we can modify my constructions to obey these conditions without too much trouble. I'll edit when I get some time.  
> **username_1**: @ErelSegal-Halevi I'm actually having a bit of trouble with the second condition, but I don't see the motivation for introducing it. It doesn't hold in the usual setting. You could have a short initial path with a big jump to reach $x$, while a longer initial path would have made that final step small enough to compensate.  
> **username_0**: In my application, all paths with the same length L essentially end in the same point (this is why the next leg only depends on L and on i). Does this monotonicity condition make the problem polynomial-time?  

---

### Answer by username_0 on 2024-02-17. Score: 1

The similarity to Travelling Salesman confused me: the more relevant problem is [single-machine scheduling with non-constant job lengths](https://en.wikipedia.org/wiki/Single-machine_scheduling#fatigue). In particular, [this paper](https://www.sciencedirect.com/science/article/pii/S0377221702009098) surveys many scheduling problems in which the job length depends on the time in which it starts. The most relevant one seems to be [this paper](https://onlinelibrary.wiley.com/doi/abs/10.1002/(SICI)1520-6750(199808)45:5%3C511::AID-NAV5%3E3.0.CO;2-6). In their model, the length of job $j$ is $p\_j$ if it starts before some due-date $d$, and $p\_j+b\_j\*(s\_j-d)$ if it starts at time $s\_j > d$. In our notation, this can be written as:

$$
f(L,i) = L + p\_i \text{ if $L\leq d$}
$$

$$
f(L,i) = L + p\_i + b\_i\cdot (L-d) \text{ if $L> d$}
$$

It satisfies both conditions, and the authors prove that the problem is NP-hard.


---

