Questions regarding the complexity of a particular algorithm or relations among time-bounded complexity classes

learn more… | top users | synonyms

-3
votes
0answers
31 views

Hash table key-data pairs insertions and search time complexity

Consider a hash table with n entries. Let h be an arbitrary hash function. What is the worst case time complexity of inserting p key-data pairs and looking up q key-data pairs in this hash table using ...
0
votes
0answers
16 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
123 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
157 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 ...
7
votes
1answer
157 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 ...
-4
votes
0answers
38 views

What would be a theoretical time complexity for sorting where you can only swap/compare neighboring elements? [closed]

Can you point me to a link on an academic paper regarding this? Thank you.
2
votes
0answers
165 views

Does $P\neq NP$ imply any larger separation?

I've asked a similar question in cs.se, but didn't get a satisfying answer. Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem? Obviously, it means ...
4
votes
0answers
118 views

Deciding transitivity of a directed acyclic graph [duplicate]

Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?
13
votes
3answers
914 views

How much time to recognize palindromes in logarithmic space?

It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time ...
4
votes
1answer
59 views

Complexity of generically inverting a class of near linear monotonic functions

Given a monotonic increasing function $f(\mathbb{N}) \rightarrow \mathbb{N}$ and a slack function $a(\mathbb{N})\rightarrow \mathbb{N}$, where $f(n) = n \pm O(a(n))$; how many calls to $f$ do we ...
2
votes
1answer
116 views

Subset Sum bounds

Are there any bounds for the subset problem with respect to the number of the terms involved in the sum and the range of the possible values?For example looking for some 2 terms whose sum equals 3 you ...
2
votes
1answer
109 views

Complexity of determining unique elements of each cycle in a permutation

It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation. But suppose that we know ...
7
votes
3answers
338 views

Can one automate algorithmic analysis?

Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a ...
9
votes
0answers
303 views

Fundamental assumptions in complexity analysis

I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as ...
6
votes
1answer
103 views

What is the fastest algorithm for Weighted Planar Max Cut

In 1990's, the paper Unifying Maximum Cut and Minimum Cut of a Planar Graph described an $O(n^{3/2}\log n)$-time algorithm for Weighted Planar Max Cut, a landmark in the field. Recently, this paper ...
2
votes
0answers
86 views

How is the complexity of PCA $O(\min(p^3,n^3))$?

I've been reading a paper on Sparse PCA, which is: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf And it states that, if you have $n$ data points, each represented with $p$ features, ...
5
votes
1answer
97 views

Computational Complexity of the Divisor summatory function

The divisor function $d(n)$, is the number of $(a,b)\in\mathbb {N^+}^2$ such that $a\times b =n$. For example, $d(2)=2$ because $2=1\times 2=2\times 1$ and d(6)=4 because $6=1\times 6=2\times ...
1
vote
1answer
68 views

Calculation of Recursive Spawning

I'm reading the book Introduction to Algorithms (Cormel et al., 2009) on the chapter about multithreaded algorithms, and I'm confused about the following: We must also account for the overhead of ...
1
vote
2answers
198 views

Task Multithreading analysis for a Divide and Conquer algorithm

Suppose an algorithm that receive an input array of $n$ elements and it performs a task over each element. All tasks are independent and take $O(k)$ each (being $k$ a variable). Since all tasks are ...
11
votes
3answers
442 views

Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

I'm seeking an efficient algorithm for the problem: Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$. Output: The number $n$. Question: Can we compute $n$ from ...
-1
votes
1answer
379 views

Time complexity analysis of random forest and k-means?

I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where $n$ is the number of points, $K$ is ...
6
votes
2answers
426 views

Is there any task where classical computers outperform quantum computers?

Everybody knows that there are whole classes of problems which quantum computers are able to solve much faster (i.e. with fewer instructions) than classical computers. Is there any problem for which ...
-3
votes
2answers
282 views

Compute Time Complexity of Neural network, SVM and other classification algorithms

I would like to know what is the asymptotic time complexity analysis for general models of Back-propagation Neural Network, SVM and Maximum Entropy. Does it just depend on number of features included ...
1
vote
0answers
129 views

Time complexity of clustering based on random walk

What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph? Can I use the complexity of eigen vector computation for this purpose? The ...
3
votes
0answers
79 views

Constant time search for rod segment

(I tried to ask at SO but maybe this has more to do with the CS theory.) Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it ...
-1
votes
1answer
489 views

Flood fill vs depth first search

Is the flood fill algorithm the same as depth first search? If not, how do they differ in complexity?
19
votes
6answers
728 views

Advanced techniques for determining complexity lower bounds

Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level. Beyond the "simpler" ...
4
votes
0answers
267 views

How are lower bounds for computational complexity proved? [closed]

As the title says, how are lower bounds for computational complexity proved? I'm interested why it is possible to say that a certain algorithm cannot run in faster time than some lower bound. ...
1
vote
0answers
88 views

Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

I was reading this paper, about the complexity of decision problems for reversal bounded counter machines. I got to Theorem 1 on Page 6. The theorem shows that there's a log-space NTM which can ...
4
votes
1answer
155 views

state-of-the-art bit complexity of the determinant

I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits. I would like to know what is the ...
11
votes
0answers
145 views

the largest element of a matrix product

Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to ...
0
votes
0answers
109 views

Is there a way to transform a Turing machine into an oblivious turing machine that decides the same langauage?

Suppose you have turing machine M that decides L. Is there a simple way to convert this turing machine into an oblivious turing machine M' that decides the same language? My intuition says yes but i ...
3
votes
1answer
119 views

Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?

In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum ...
5
votes
1answer
172 views

#P-Completeness of the Hosoya Index

The description from Wikipedia mentions that it is #P-Complete to compute, but there are methods. What is a layman's explanation to this?
2
votes
1answer
243 views

Finding max of two elements in linear time with restriction

I have a matrix in the following form: ...
0
votes
3answers
506 views

How can you prove that a problem is not solvable in a certain time complexity?

One of the most interesting questions in computer science is of course whether $P = NP$ or $P \neq NP$. If one wants to prove that $P \neq NP$ one can try to prove that an NPC problem is not solvable ...
15
votes
0answers
255 views

Runtime of Grover's algorithm

What is the time complexity (not query complexity) of Grover's algorithm? It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration ...
11
votes
2answers
429 views

Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice ...
2
votes
0answers
142 views

Open questions about linear-time

What are some interesting open or solved-but-hard questions around problems having linear-time solutions? Ala riffle shuffles. I'm especially curious about problems which people believe to be ...
11
votes
2answers
326 views

What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
8
votes
1answer
323 views

Can we get a sorted list from a sorted matrix in $O(n^2)$

I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$. I proceed by assuming that it can be done ...
1
vote
0answers
322 views

Finding two vertices with the most/least common neighbors

I am not a computer scientist so please bear with me if this is a naive question. Take any graph, pick a set S of vertices (by some criteria or random). Find two vertices in set S with the ...
3
votes
0answers
171 views

Insertion and deletion operations for Turing machines

A Turning machine with insertion and deletion operations can be simulated by an ordinary Turing machine with a quadratic time cost. Do we know how insertion and deletion fit into the polynomial time ...
1
vote
0answers
172 views

Nondeterministic linear time vs. the deterministic time hierarchy

How much is known about nondeterministic linear time? I'm aware that $$ \mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$ Is there an $m > 1$ so that $\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$? ...
15
votes
11answers
2k views

Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form? I understand lots of things that might cause a log ...
5
votes
1answer
146 views

What is the complexity of model checking Process Logic (LTL fragment)?

Process Logic is a modal logic allowing to reason about temporal properties of programs. Its formulae take the form similar to (Propositional) Dynamic Logic $[P]\phi$, with $P$ being a program (think ...
4
votes
0answers
72 views

Real-time countable vs fully time-constructible

Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a ...
12
votes
1answer
420 views

Equivalent definitions of time constructibility

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ ...
0
votes
0answers
41 views

Algorithmically compute a reasonable bound on the runtime of an algorithm [duplicate]

Possible Duplicate: Are runtime bounds in P decidable? (answer: no) Originally asked on SO: http://stackoverflow.com/questions/13371025 I have seen many questions asking if this ...
1
vote
0answers
106 views

Computational Complexity of RESTRICTED primality testing

Input: Any number $n \in \mathbb{Z}^+$ that can be represented in the form of $n = 2^a + b,\ |b|= c $. output: YES if $n$ is prime , else NO . Now, length of binary input is $\log(a) + O(1)$ which ...