Unanswered Questions
737 questions with no upvoted or accepted answers
32
votes
1
answer
886
views
Largest set of cocircular points
Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior).
This can be done in $O(n^3)$ easily ...
CommunityBot
- 1
26
votes
1
answer
784
views
Complexity of deciding whether there is a winning strategy in the following game
The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 \...
12
votes
1
answer
5k
views
Finding the longest repeating subsequence
Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
- 280k
10
votes
0
answers
1k
views
Complexity of Sorting Integers on a Multitape Turing Machine
How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access.....
- 5,962
9
votes
0
answers
209
views
Complexity of frog game on graphs is exponential, or can we do better?
Frog game initializes by placing one frog on every vertex of a simple connected graph $G$ with $n$ vertices. A move consists of moving all $x\gt 0$ frogs from one vertex to another non-empty vertex to ...
- 117
9
votes
0
answers
784
views
How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?
I'm stuck on problem 9.4 from The Nature of Computation which reads:
Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
- 1,058
9
votes
0
answers
372
views
P vs NP and the Time Hierarchy
Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$?
There reason I ask this is that I assume the following:
$$P=NP \implies \forall k\ \exists j.\ \...
CommunityBot
- 1
8
votes
0
answers
1k
views
Non-deterministic time hierarchy theorem: universal TM overhead
I am currently reading the book of Arora and Barak on computational complexity.
In the third chapter (p69-70), two classic theorems regarding time complexity hierarchies are introduced:
$\left[f(n)\...
- 81
8
votes
0
answers
647
views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
CommunityBot
- 1
7
votes
0
answers
172
views
Overlap Maximization problem
Here's the problem:
I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
- 378
6
votes
0
answers
115
views
Polynomial time algorithms for graphs and cycles
For a given undirected graph $G$ , let $ c(G) $ denote the length of the longest cycle in $ G $ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
- 7,603
6
votes
0
answers
97
views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
CommunityBot
- 1
6
votes
0
answers
1k
views
Time complexity of obtaining the support set of an unsorted sequence?
Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
- 1,025
6
votes
0
answers
327
views
Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)
Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$.
Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but ...
CommunityBot
- 1
6
votes
0
answers
130
views
Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments
One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine.
Is there a ...
CommunityBot
- 1