Time complexity of decision problems or relations among time-bounded complexity classes. (Use [tag:analysis-of-algorithms] for the time taken by particular algorithms.)

learn more… | top users | synonyms

3
votes
1answer
108 views

maximizing inner product

Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each, how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} ...
0
votes
0answers
53 views

How often can a linear speed sort succeed? [migrated]

Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$. What kind of bounds can we place ...
0
votes
0answers
22 views

Explanation on Time Complexity in information retrival in nearest neighbor search

My problem is related to the approximate nearest neighbor search. I found a useful link Calculating the distance to the kth nearest neighbor for all points in the set which says that the search takes ...
-5
votes
0answers
83 views

Example of polynomial speedup over previously known exponential time complexity

In the IARPA-BAA-15-13, the term "polynomial speedup over exponential time complexity" is defined as follows. My question: Is there any example of polynomial speedup over exponential time ...
1
vote
0answers
30 views

Best Asymptotic Complexity for Persistent Union Find

In this paper https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf, they claim to have a practically fast persistent union-find data structure for most use-cases, but it's still not polylogarithmic ...
-3
votes
2answers
98 views

Code Optimization using Theory of computations [closed]

Project will take valid C Program as input and it optimizes the code so that time efficiency will be improved. Some of methods what I thought are as follows:- • Try to avoid if-else condition if ...
1
vote
0answers
107 views

Computing $a^e \mod p^n$ Efficiently

It is well known that we can compute: $$ a^e \mod m $$ in $O(\log e \log ^2 m)$ bit operations (assuming multiplication $nm$ in $O(\log n \log m)$ time) via exponentiation by squaring. I am wondering ...
-5
votes
1answer
87 views

What is the complexity of the fastest method of k-coloring any graph? [closed]

I heard brute-force is the only method. Is there any other way? Is there a way to prove that the complexity cannot be exponential?
3
votes
1answer
68 views

Efficient all pair bottleneck computation for a tree

Consider a weighted tree $T = (V,E)$. The bottleneck weight for a pair of vertices $v_1,v_2 \in V$ is the highest weight of the edges on the unique path from $v_1$ to $v_2$ (if $v_1 = v_2$ it is 0). ...
3
votes
0answers
42 views

First-order methods for solving SDP with geometric convergence or better

Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?
5
votes
2answers
138 views

Popular average-case complexity assumptions

Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?
0
votes
1answer
54 views

How can I find tight asymptotic bounds for this half-history recurrence relation?

The recurrence relation $\forall n\in\mathbb{N}\cup\{0\}$ is $T(n)=\Theta(n^2)+2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{T(i)}$, with base case of $T(0)=0$. Fairly simple tree analysis shows that ...
7
votes
1answer
207 views

Are there more polynomial time problems with complexity lower bounds?

I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below. Exponential Lower Bounds: Claim: If ...
15
votes
2answers
336 views

Is there a non-deterministic linear time algorithm for CNF-SAT?

The decision problem CNF-SAT can be described as follows: Input: A boolean formula $\phi$ in conjunctive normal form. Question: Does there exist a variable assignment that satisfies $\phi$? I'm ...
14
votes
3answers
531 views

Nontrivial problems solvable in constant time?

Constant time is the absolute low end of time complexity. One may wonder: is there anything nontrivial that can be computed in constant time? If we stick to the Turing machine model, then not much can ...
20
votes
1answer
742 views

Time complexity with irrational exponent?

Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?
1
vote
0answers
49 views

Complexity of QBF with Restrictions on Models [closed]

Do you know the complexity of the following decision problem? Given a quantified boolean formula (QBF) $\phi$ with $2n$ free variables with $n\in\mathbb{N}$. Is there a satisfying assignment s.t. ...
3
votes
0answers
43 views

Is this permutation-sum problem NP-complete? [duplicate]

A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In ...
4
votes
0answers
231 views

Is this permutation-sum problem NP-complete?

A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In ...
1
vote
1answer
101 views

Assignment of values for a set

Consider the following problem: Input: the vertices of two $n$ dimensional axis-parallel cubes: $\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and $\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$. ...
10
votes
2answers
159 views

The complexity of finding a Borsuk-Ulam point

The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$. Simmons and Su (2002) describe a method ...
4
votes
1answer
71 views

Approximate matching in table of integer vectors

Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving. I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain ...
6
votes
2answers
179 views

P-complete decision problems about integers

Are there any known examples of P-complete decision problems which take as input a single integer? (non-unary, as unary feels like un-naturally forcing the issue) It feels like there are many ...
6
votes
1answer
155 views

Hierarchy theorem for NTIME intersect coNTIME?

$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap ...
3
votes
0answers
75 views

Complexity of eigenvaue problem

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices). What is the best time lower bound it is known? ...
11
votes
2answers
230 views

What is an equivalent definition of mP/poly in terms of a Turing machine?

P/poly is the class of decision problems solvable by a family of polynomial-size Boolean circuits. It can alternatively be defined as a polynomial-time Turing machine that receives an advice string ...
3
votes
2answers
264 views

Runtime of Tucker's algorithm for generating a Eulerian circuit

What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...
2
votes
0answers
117 views

Complexity of Knapsack-type problem with applications to computational workflows

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
10
votes
1answer
354 views

Simple path on dag with backward edges

What is the complexity of the following problem ($\in$ P? NP-hard?): Input: a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$. ...
-7
votes
1answer
280 views

Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
7
votes
2answers
348 views

Generalized Geography on graphs of bounded treewidth

Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play ...
1
vote
0answers
67 views

What is the minimal known space for polytime algorithms

Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured ...
8
votes
2answers
309 views

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

In the movie Inception Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource ...
4
votes
0answers
125 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

I already posted this question here but I didn't receive an answer, so I'm posting it here as well :) Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as ...
-2
votes
1answer
156 views

Algorithm to determine if given algorithm runs in polynomial time [duplicate]

In general, the undecidability of the halting problem prohibits the general determination of an algorithm's complexity. However, I can see no reason why the halting problem prohibits one from deciding ...
2
votes
0answers
90 views

number of iterations of this algorithm (upper bound)

Let $(A, dist)$ be a finite metric space. Consider the following "$p$-center problem": given a positive integer $p$, find a subset $B$of $A$ such that $|B| = p$ and which minimizes the number $\max_{a ...
3
votes
1answer
359 views

Is the following problem in P or in NP?

Given an integer $K$, a set of tasks $T=\{a_1,b_1,\dots,a_n,b_n\}$ with sequence dependent execution times $E:T \times T \rightarrow \mathbb{N}$ and precedence constraints on $T$ of the following ...
6
votes
1answer
87 views

Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
1
vote
0answers
51 views

Computational complexity of Initial Value Problems of ODEs

Are there known results on computational complexity of initial value problems of ODEs? As my question may be somewhat vague, I want to mention that I'm mainly interested for results on the ...
2
votes
0answers
93 views

Is the problem “Binary Sorted Min Sum” already known under an other name?

A computer scientist oriented toward applications gave me the following problem: Given a positive integer $n>0$, an increasing function function $f$ and a decreasing function $g$, both ...
8
votes
1answer
385 views

DFA intersection algorithm for special cases

I'm interested in efficient algorithms for DFA intersection for special cases. Namely, when the DFAs to intersect obey a certain structure and/or operates on limited alphabet. Is there any source ...
8
votes
0answers
65 views

Finding a median in a union of sets given as sorted arrays [duplicate]

You are given $k$ sorted arrays $A_1, A_2, ..., A_k$, each containing $n$ elements. How fast can you compute the median of $A_1 \cup A_2 \cup ... \cup A_k$ ? I have a solution running in ...
0
votes
1answer
198 views

Finding $x_1,x_2,…,x_k$ such that $n=x_1!+x_2!+…+x_k!$ and $k$ is minimal [closed]

Here is a problem I'm trying to solve: Given an integer $n$ return a list $[x_1,x_2,...,x_k]$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is as low as it can be. I'm thinking of creating a list of n ...
8
votes
0answers
1k views

Time complexity of a branching-and-bound algorithm

Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching ...
2
votes
0answers
227 views

Subset sum solver. Worth continue working on this method? [closed]

I have been working in a subset sum problem solver for some time. The implementation is an exact/exhaustive search solver. The variable determining the asymptomatic growth rate is just $N$ (the ...
5
votes
1answer
219 views

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why? Details: http://en.wikipedia.org/wiki/Powerset_construction states that the ...
6
votes
0answers
79 views

Complexity of solving vs verifying in P

Thinking of (seemingly) very different complexity of finding a solution to a NP problem and verifying it as the basis of practical cryptography, I am wondering if such separation is possible among ...
2
votes
0answers
126 views

Recent insights on algorithms for 1D bin packing

This is just a general question on recent algorithms for the 1D bin packing problem. I just want to collect some information on this issue, so I’m grateful for any information. Especially heuristics ...
4
votes
3answers
125 views

Fast high-dimensional K-nearest neighbors

I'm aware of this question http://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm But it's not the same question as I'm asking. Because, Octree and its generalization are only ...
7
votes
1answer
140 views

What's the complexity of recognizing equivalence for the following relation?

Consider the set $\mathcal{M}_{m,n}(\mathbb{Z})$ of $m$-by-$n$ matrices over, e.g., integers. We say that two matrices $A$, $B \in \mathcal{M}_{m,n}(\mathbb{Z})$ are equivalent if $A$ can be obtained ...