32

No such problem is known (not with a known mathematical proof of a lower bound). Of course cryptographers would jump on it if we had one. As a result, cryptography is currently based on assumptions that we hope are true but we cannot prove (these are sometimes called "hardness assumptions"), and then we prove that if the assumption is valid, then ...


11

Other answers have given some specific examples of problems whose difficulty is conjectured to be between polynomial and exponential time, but the Time Hierarchy Theorem gives a general proof that for any time-constructible function $f(n)$, there is some decision problem which can be solved in time $f(n) \cdot log^2(n)$ but not in time $f(n)$. Namely: Given ...


3

The problem is still $\mathsf{NP}$-hard. For example, take a hard instance $G = (V,E)$ of the original maximum independent set problem. Add a new vertex set $V'$ to the graph such that $|V'| = |V|$ and $V'$ forms a complete graph. Also, there are no edges between $V$ and $V'$. Let the new graph be $G' = (V' \cup V, E')$ which is also a hard instance. And, $|...


2

Spurred by comments in Pierre Marie's answer, I'll add some clarification on the difference between type checking and type synthesis. Generally, type checking in a dependent type system is designed to be decidable up to normalization for fully annotated terms, that is, $\lambda x : T.t$ and $\Pi x : T. U$ for example (you need type annotations in other ...


2

Note that the expected running time analysis is $O(n)$. It is given in the original paper itself (Section 2). Here, I am simply analyzing the worst-case time complexity of the algorithm. Note that Part $3$ and Part $5$ are not the same. Let $T(n,r)$ denote the complexity of algorithm when $|P| = n$ and $|R| = r$. Then, Part $3$ corresponds to $T(n-1,r)$ and ...


2

The first step is to read and understand the papers. It's not always enough to read just the introduction -- you often need to read the full paper, particularly the precise statement of results and their discussion. Reading the papers will help you discover what they each actually prove, and then you will discover why the two papers are actually consistent ...


2

If I understand you correctly, I don't think such an algorithm exists. Any algorithm that uses only log space and halts could not run in exponential time, because there is at most polynomial number of unique configurations of the machine. This applies to randomized algorithms (i.e. probabilistic Turing machines) as well, because every branch of the ...


1

Let f(n, p) be the number of binary sequences with exactly P zeroes. You just calculate them in the right order and store the results: f(n, 0) = 1 for all n. f(n, p) = 0 for all p > n. f(n, p) = f(n-1, p-1) + f(n-1, p) for 1 <= p <= n. Then you add the values f(n,p) for p >= P to get the number of sequences. Enumerating them is obviously ...


1

Vertices in your tree correspond to decreasing sequences starting at $n$. We can identify each such subsequence with a subset of $\{0,\ldots,n-1\}$, and consequently, your tree contains $2^n$ vertices. Consequently, assuming the processing per node is $O(1)$, your algorithm runs in time $\Theta(2^n)$. The same method also allows us to count directly the ...


1

No. The amount of space used is upper-bounded by the running time. Each step of the Turing machine can only move one place on the tape. Therefore, $P \subseteq PSPACE$.


1

This is feasible to compute in fairly fast (polynomial) time with linear programming. This problem seems like a poster problem for linear programming where you specify a set of equalities and inequalities, e.g. tomato between 0 and 100 grams, apple between 0 and 100 grams and then if each gram of a tomato has 1 mg of vitamin X and each gram of an apple has 2 ...


1

I don't think this is some historical quote that was famously said by someone, or that needs to be attributed to someone who said it. It is just a mathematical fact. I imagine many people have made a similar observation. Your question is a little like asking "Who said first that 2+2=4?" You'd probably give me a funny look if I asked that ...


1

It is known that $BQP \subseteq PSPACE \subseteq EXP \subseteq NEXPTIME$. If $BQP = NEXPTIME$ then $PSPACE = EXP $ and $ EXP = NEXPTIME $. This would imply $L = P$ and $P = NP$.


1

The answer depends on the coding of $n$. The set $\{(M,x,1^n) | \text{ TM } M \text{ accepts }x \text{ within } n \text{ tape space } \}$ is $PSPACE$-complete. But the set $\{(M,x,n) | \text{ TM } M \text{ accepts }x \text{ within } n \text{ tape space } \}$ where $n$ is binary coded is $EXPSPACE$-complete.


Only top voted, non community-wiki answers of a minimum length are eligible