Questions regarding the complexity of a particular algorithm or relations among time-bounded complexity classes
2
votes
0answers
10 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 ...
-6
votes
0answers
39 views
CalculatorVSCellPhone [closed]
"calculator or calculating machine, device for performing numerical computations; it may be mechanical, electromechanical, or electronic. The electronic computer is also a calculator but performs ...
-1
votes
0answers
42 views
Using software to calculate complexity of algorithm
I am somewhat a beginner, I have often seen complexity being calculated for various algorithms but they never actually gave me very clear idea about how it is done.
can someone please point some ...
0
votes
0answers
87 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 ...
-1
votes
0answers
30 views
Time complexity in Big O notation for Harmonic series with first k terms missing [migrated]
Firstly, let's suppose there exists an algorithm where i iterates from 1 to n, spending n^2/i time in each iteration.
Thanks to the well known O(logn) upper bound for the Harmonic series, the big O ...
2
votes
1answer
90 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 ...
4
votes
1answer
137 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
0answers
55 views
Finding average distance while travelling on an infinite wall [migrated]
Ok here is the question:
There is an infinite wall with a hole somewhere, you are placed on that wall at a random position. Let the distance between your initial position & hole be X. Find the ...
2
votes
1answer
166 views
Finding max of two elements in linear time with restriction
I have a matrix in the following form:
...
2
votes
3answers
420 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 ...
11
votes
0answers
202 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 ...
10
votes
1answer
224 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
129 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 ...
9
votes
0answers
146 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
232 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
186 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
125 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
132 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)$? ...
14
votes
11answers
1k 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
106 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
59 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
335 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
37 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 ...
0
votes
0answers
73 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
308 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 ...
4
votes
0answers
151 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
94 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
224 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, ...
6
votes
2answers
465 views
Complexity of the halting problem
One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind:
...
4
votes
0answers
124 views
Complexity of computing logarithm of a prime power
Suppose $n = p^k$ for some prime number $p$ and some non-negative integer $k$. What is (the best-known upper bound on) the complexity of computing $k$ on input $n$ (given in binary)? It is important ...
6
votes
0answers
62 views
Cell probe model vs transdichotomous ram
can someone explain me the difference between those two (cell probe model and transdichotomous ram)?
In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of ...
3
votes
1answer
230 views
Computational complexity of classifying with an already-trained SVM
If I have a support vector machine which has already been trained, what is the computational complexity of classifying a new example using that machine? I care about both time and space complexity.
...
10
votes
3answers
424 views
Linear time in-place riffle shuffle algorithm
Is there a linear time in-place riffle shuffle algorithm? This is the algorithm that some especially dextrous hands are capable of performing: evenly dividing an even-sized input array, and then ...
7
votes
0answers
178 views
How quickly can we find an arbitrary digit in multiplication?
In considering an answer to this question, I once again wondered how quickly we could find a digit in multiplication.
We may first consider previous results. Finding the least significant digits is ...
9
votes
1answer
151 views
similar matrices
Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
21
votes
1answer
839 views
Is there a proof that addition is faster than multiplication?
The best upper bound known on the time complexity of multiplication is Martin Fürer's bound $n\log n2^{O(\log^* n)}$, which is more than linear time complexity of addition. Do we have a proof that ...
2
votes
0answers
398 views
Tricky big-O calculation
I have a recursive algorithm in which the time for each step depends on the time for smaller steps. Essentially a structure is built at steps 1, 2, ..., n which must be searched at larger heights:
$$
...
14
votes
2answers
370 views
To what extent can an algorithm predict the time complexity an arbitrary input program?
The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs.
I can, however, certainly write a program that can ...
4
votes
2answers
130 views
Function with space-depending computation time
Does a function exist which is easily computable for one space capacity and is hard to compute for another? I am looking for a function which can be computed in polytime when available space is at ...
0
votes
1answer
318 views
$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$?
Can this statement be confirmed or disproved:
$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$
[Question changed to use Kaveh's brilliant formulation.]
Here the NDTM ...
12
votes
2answers
488 views
Gaussian Elimination in terms of Group Action
Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to ...
6
votes
2answers
217 views
Vertex subset of maximum size
I was wondering if this problem has a name and/or it has been already studied.
Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$ :
Does ...
10
votes
0answers
263 views
Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.
I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
5
votes
1answer
124 views
Can we do joins in NC?
Suppose we want to join two relations on a predicate. Is this in NC?
I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
1
vote
0answers
121 views
What's the complexity of Spearman's rank correlation coefficient computation?
I've been studyin' the Spearman's rank correlation coefficient.
If computed for two list that have both size N, what's the complexity of the algorithm?
O(N) ?
thanks
11
votes
1answer
1k views
The computational complexity of matrix multiplication
I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by ...
6
votes
3answers
677 views
Algorithms with finite expected running time and infinite variance
I am working on an algorithm for which the running time is a random variable $X$ that has finite expected value, but infinite variance. Are there examples of other algorithms for which this is the ...
-10
votes
2answers
496 views
Are sorting algorithms approaching linear time? [closed]
I see some algorithms can do sorting in O(nloglogn) time. Is it reasonable to assume that as research progresses, more and more will be done to logarithm the extra time e.g. next research will produce ...
0
votes
0answers
211 views
CS complexity of famous complex (“fast-growing”) mathematical functions [closed]
there is a branch of mathematics that has developed roughly in parallel with CS complexity theory that studies "complex" in the sense of "hard-to-compute" functions (because of the property of ...
1
vote
1answer
224 views
Worst-case asymptotic-complexity of the Set-cover problem?
What's the worst-case asymptotic-complexity of the Set-cover problem in Big O notation?
I've been developing some novel techniques to try and solve this problem but am having trouble finding the ...
