Computational complexity, a part of theoretical computer science.
5
votes
1answer
221 views
What is the significance of the graph isomorphism problem?
It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an ...
4
votes
1answer
235 views
Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?
I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this:
Strassen’s algorithm is not at all obvious. (This might be the biggest ...
1
vote
2answers
91 views
How can the following language be determined in polynomial time
I'd love your help with understanding why the following is decidable and can be determinate in polynomial time ($L \in P$).
$L=\{(\langle M \rangle,w)|M$ is a Turing machine with Q states and one ...
0
votes
2answers
44 views
Complexity classes and number of problems
Will every complexity class contain infinite number of problems?
If they do not, do common complexity classes (e.g. P,NP,PSPACE,EXPTIME,EXPSPACE etc.) contain infinite number of problems?
0
votes
1answer
101 views
Determining computational complexity of stochastic processes
I have an program which implements a Markov chain Monte Carlo process on a system of N bits, stopping when the process converges. Let's use T to denote the average number of steps made by the Markov ...
13
votes
1answer
1k views
$e^{e^{e^{79}}}$ and ultrafinitism
I was reading the following article on Ultrafinitism, and it mentions that one of the reasons ultrafinitists believe that N is not infinite is because the floor of $e^{e^{e^{79}}}$ is not computable. ...
3
votes
1answer
1k views
Computational complexity of least square regression operation
In a least square regression algorithm, I have to do the following operations to compute regression coefficients:
Matrix multiplication, complexity: $O(C^2N)$
Matrix inversion, complexity: ...
6
votes
1answer
761 views
Definition of time-constructible function
What would be an intuitive notion of time-constructible functions ? Is there a function which is not time-constructible?
In my own words I would say a function is time-constructible when 1. it is ...
0
votes
3answers
176 views
Using $O(n)$ to determine limits of form $1^{\infty},\frac{0}{0},0\times\infty,{\infty}^0,0^0$?
Is it sufficient to use $O(n)$ repeatedly on $1^{\infty},\frac{0}{0},0\times\infty,{\infty}^0,0^0$ to get determinate forms?
For example if we look at $\frac{0}{0}$ then $$\frac{O(f(n))}{O(g(n))}$$ ...
5
votes
1answer
445 views
Why are Hornsat, 3sat and 2sat not equivalent?
I have been reading a little bit about complexity theory recently, and I'm having a bit of a stumbling block. The horn satisfiability problem is solvable in linear time, but the boolean satisfiability ...
2
votes
3answers
209 views
Factoring extremely large integers.
The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
1
vote
2answers
53 views
Sequences and Languages
Let $U$ be the following language. A string $s$ is in $U$ if it can be written as:
$s = 1^{a_1}01^{a_2}0 ... 1^{a_n}01^b$,
where $a_1,..., a_n$ are positive integers such that there is a 0-1 ...
5
votes
2answers
222 views
Is there a log-space algorithm for divisibility?
Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...
5
votes
1answer
235 views
Can a Pratt certificate for a prime be found in polynomial time?
Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...
4
votes
3answers
245 views
How complicated is the set of tautologies?
Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$.
How ...
