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
43 views

Karatsuba's algorithm smart step analysis [closed]

I have a problem that I want to solve. I really tried but it does not budge. If the input is of size n for Karatsuba's algorithm We have three steps in Karatsuba's algorithm: 1) Recursively compute ...
4
votes
0answers
72 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 ...
-3
votes
1answer
84 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
29 views

Design a non-polynomial time PAC algorithm that learns the class of all boolean circuits?

Setting. Suppose we relaxed the constraint that PAC learner uses polynomially evaluable hypothesis class $\mathcal{H}$. Instead let $\mathcal{H}$ be the class of all Turing machines (not neccessarily ...
1
vote
0answers
61 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 ...
-4
votes
0answers
50 views

Running time of partial algorithms [migrated]

What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts? Assume, if necessary, that the halting problem ...
3
votes
1answer
354 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 ...
5
votes
1answer
66 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
37 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
84 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
214 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
64 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 ...
-1
votes
1answer
174 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 ...
7
votes
0answers
135 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
145 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
99 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
70 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
64 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
92 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 ...
6
votes
1answer
103 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 ...
-2
votes
0answers
39 views

Little o Notation [closed]

I understand the little-oh notation a bit, but there is still some confusion. By definition, I get that f ∈ o(g) means that |f(x)/g(x)| approaches 0 as x approaches infinity. I also read somewhere ...
-1
votes
1answer
98 views

Using master theorem when there is a constant in the recursive term [closed]

Is it possible to use the master theorem to find the asymptotic growth of a function of the form: $$T(n) = aT(\frac{n}{b}+c)+f(n)$$ Where $c$ is a constant. Can we safely ignore this constant and use ...
6
votes
1answer
2k views

Magic constant to solve NP-complete problem in polynomial time

Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial ...
6
votes
2answers
346 views

Complexity of finding even cuts for a graph

Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in ...
7
votes
3answers
251 views

Total orders which are the transitive closure of a set in P

I am wondering if there is an example of the following form. It seems highly plausible that there should be but I am struggling to come up with one. Consider $T \subseteq \mathbb{N}^2$, a set ...
3
votes
0answers
33 views

Limits of parallel computing with local connections?

There are successes with an increasing numbers of individual computational units in GPUs or as processor cores. Given someone made the effort to build a huge array of processors which - however - can ...
2
votes
1answer
160 views

Max flow: either saturate an edge or avoids

Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half ...
-1
votes
1answer
178 views

Is the running time of Boyer-Moore linear?

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)? Are there any sublinear ...
2
votes
1answer
163 views

Time complexity of d-dimensional convex hull

Consider the convex hull problem in $\Re^d$: Input: a list of $n$ points $S$ in $\Re^d$, Output: the vertices of the convex hull of $S$. What is the best lower bound on the time complexity of ...
1
vote
0answers
133 views

proving speedup phenomenon does not apply to any open complexity class separations

Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question. the Blum speedup ...
12
votes
3answers
2k views

Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart. ...
1
vote
2answers
201 views

What is the asymptotic time complexity of the number of steps of “Half Or Triple Plus One” ( HOTPO)?

The "Half Or Triple Plus One" process goes as follows: start with $x=n$ for some value of $n$ if ($x$ is odd) $x = 3x+1$ else $x = \frac{x}{2}$ if ($x$ > 1) goto (2) ...
0
votes
0answers
49 views

Known time complexity advantage of quantum algorithms over classical algorithms [duplicate]

I know that this question may depend on how one formulates each complexity class, but in general, what time complexity advantage does quantum algorithms have over classical algorithms?
2
votes
1answer
67 views

Efficient Shamir secret sharing reconstruction

Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the ...
0
votes
1answer
130 views

maximum weighted 2D coverage problem by a rectangle

Let $P=\{p_1,\ldots,p_n\}$ be a set of $n$ points in a 2D plane, that is $p_i\in \mathbb{R}^2$, $\forall i=1,\ldots,n$. Each point, $p_i$, is associated with a weight, $w_i \geq 0$. Imagine a ...
13
votes
4answers
362 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
2
votes
1answer
122 views

Is there an additive time hierarchy theorem?

I would like something like this to be true: Conjecture: There is a function $g(n)$ such that for all functions $f(n)$ (perhaps satisfying some reasonable properties, like time-constructability), ...
4
votes
3answers
122 views

Remove unneeded atoms in CNF minimalization (SAT preprocessing)

This might be a very basic question. I am interested in all atoms of a propositional formula that can be removed from a particular formula, while the derived formula has the same satisfiability ...
4
votes
3answers
372 views

Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

An "algorithm" for calculating $ax+b$ would take the steps Calculate $a$ times $x$ Calculate $b$ plus the result of previous line. But if the values of $a$ and $b$ are known, can we create a more ...
8
votes
0answers
212 views

Linear space language that requires exponential time without ETH

The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$ requires ...
3
votes
1answer
113 views

Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers

It is often said that memoization brings the complexity of recursive-descent parsers from exponential to polynomial. However, I had a hard time finding an example grammar that triggers the exponential ...
1
vote
1answer
117 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...
8
votes
1answer
171 views

Multidimensional arithmetic progression variant

For $\vec{d} \in \mathbb{N}^n$, let $Q(\vec{d}) \subset \mathbb{N}^n$ be the set of vertices of the $n$-dimensional cube scaled in the direction of the $i$-th coordinate by $d_i$, i.e. $Q(\vec{d} = ...
2
votes
2answers
119 views

Number of SAT checks that are needed to find all combinations of subset of boolean variables of a propositional formula

Please mind that I sometimes lack formal mathematical knowledge and English is not my first language, so I might miss the right words. Please change the tile if needed. Also, I have choosen this site ...
6
votes
1answer
235 views

Distinguishing between two coins

It is well known that the complexity of distinguishing an $\epsilon$ biased coin from a fair one is $\theta(\epsilon^{-2})$. Are there results for distinguishing a $p$ coin from a $p+\epsilon$ coin? I ...
1
vote
2answers
265 views

Lower-bound of a decision problem [closed]

What's the lower-bound of the decision problem that decides: Whether there is at least one element A[i] such that A[i] = i in a sorted array A of non-negtive integers? (An example is A = ...
0
votes
0answers
21 views

What's the official name for time-driven parallel informed sorting methods?

If you have a set $\Delta = \{A,B,C,D,E,...\}$ and you want to sort $\Delta$ based on a certain quality of the elements $\in \Delta$, then you can use a certain classification or ranking algorithm $R$ ...
0
votes
0answers
521 views

Most efficient algorithm to search an unsorted array with a very precise data structure

(I apologize in advance if this question sounds a bit practical, but I suspect it might have an interesting theoretical aspect.) I have a (large) array of data, not completely sorted, but with which ...
9
votes
0answers
198 views

Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”. On the bottom of page 2 they remark that the results of Kannan imply that ...
8
votes
1answer
169 views

Consequences of nondeterminism speeding up deterministic computation

If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e. for some function $t \in n^{\omega(1)}$, $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$, then if follows from the ...