Ответ 1
Мы можем ограничить длину пути сверху, отметив, что если такой путь существует, он должен состоять из смеси простого пути и некоторых циклов. Каждый из этих путей может иметь не более длины n. Для каждого цикла мы можем эффективно применить вектор, который соответствует изменению, которое происходит, пройдя один из таких циклов. Мы можем построить только m циклов, которые линейно независимы друг от друга (обратите внимание, что нам может потребоваться идти в обоих направлениях), что достаточно для покрытия любого вектора, который стоит сам простой путь, поэтому мы можем разрешить любой остаток, пройдя каждый цикл нужное количество раз (это зависит от стоимости такого преимущества). Количество раз, которое мы должны пройти через различные циклы, ограничено сверху чем-то, эквивалентным наименьшему общему множителю для эффективных длин каждого из векторов эффектов различных циклов, который имеет (грубую) асимтотическую оценку O(n^2m). Если эта верхняя граница справедлива (вы можете построить случай, достаточно близкий к нему, разделив n на m областей размером примерно n/m, а затем сделать так, чтобы их длины простых чисел отсчитывались от n/m, а затем объединить их зависимости, что даст ´O ((n/m) ^ m) '), тогда решение будет иметь экспоненциальный размер, что означает, что любой алгоритм, использующий (и сообщающий) несжатые длины пути, не поместится в PSPACE (который является надмножеством P и NP).).