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

-2
votes
0answers
23 views

How can I understand better the Libra method for arrays?

The Libra method as I learned can help with finding the smallest sum in an array. When given an array, you use two pointers : One to the first index and one to the last index.And each iteration you ...
-1
votes
0answers
15 views

Dynamic Modeling Improvement Suggestions

I'm encountering a dynamic modelling problem. I've tried a lot of methods but it seems that all of them are of time complexity O(MNK), like the basic algorithm. I wonder if any guys can make some ...
4
votes
0answers
110 views

Testing for satisfiability of a system of linear equations over GF(2)

Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$. Is it easier to check satisfiability of the ...
6
votes
0answers
58 views

Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree

A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how ...
3
votes
1answer
134 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
25 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 ...
1
vote
0answers
35 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 ...
1
vote
0answers
108 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
90 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
76 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
45 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
140 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
55 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 $T(n)\...
7
votes
1answer
215 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
350 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
537 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
745 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
52 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 particular,...
4
votes
0answers
252 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 particular,...
1
vote
1answer
102 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
161 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
72 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 0-...
6
votes
2answers
183 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
157 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 \cc{coNTIME}(...
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
234 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
313 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
118 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
358 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
434 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
354 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
70 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 bounds?...
8
votes
2answers
311 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
129 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
169 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
90 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
94 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
392 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
203 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
243 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
248 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 worst-...
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
134 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
126 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 ...