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

learn more… | top users | synonyms

-4
votes
0answers
31 views

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

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

Time complexity [closed]

1. template void reverseLinkedList(list &lst, int start, int end) { if(start < end) { char temp = lst[start]; lst[start] = lst[end]; lst[end] = temp; ...
2
votes
0answers
162 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
912 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
58 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
108 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
108 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
337 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
302 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
102 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
95 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
67 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
196 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
441 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
374 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
425 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
259 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
128 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
475 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
722 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
144 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
118 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
503 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
254 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
428 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
325 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
320 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
170 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
170 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
419 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 ...
12
votes
1answer
322 views

Optimal NP solvers

Fix $X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$ an NP-complete search problem e.g. the search form of SAT. Levin search provides an algorithm $L$ for solving $X$ which is optimal in ...
5
votes
0answers
334 views

What is computational complexity of calculating the Variance-Covariance Matrix?

I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector ...
2
votes
1answer
106 views

Speed-up of universal computation by caching

A universal computer is a program that can execute any other program. It is interesting to ask whether there are "booster" computers that execute programs faster than they execute "on their own". In ...
0
votes
1answer
466 views

Near-Sort quicksort algorithm faster than O(nlgn) [closed]

Here, we define a nearly-sorted array with k-sized error, as this: Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices. For example: 1, 2, 3, 6, ...