I was reading the book by Kozen-Theory of Computation. There is a statement that Turing machine is the best model for defining basic time and space complexity because atleast for higher levels of complexity the definitions are robust and reflect fairly accurately our expectations of real life computation. I did not clearly understand the statement. Why is definition said to be robust?
Tag: complexity
complexity theory – Functions with small support have small circuits
I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand:
Show that if a function $fcolon {0,1}^n→{0,1}$ has a support of size $k$, then it can be decided by a circuit of size $O(nk)$.
I understand that for any binary functions of this sort, the maximal size of the circuit is $O(n2^n)$, and I have a feeling that this could be useful for proving the statement, but I am not exactly sure where to proceed from there. Furthermore, I also understand that the “support” referred to in this question is actually the language defined by the function, but again, this leads me nowhere.
Any help on this would be much appreciated.
Time complexity for nxn determinant?
Method for finding the nxn determinant of a matrix is the method of simplifying by row or col.
Find Time complexity for it.
My try:
(n-1)! + (n-1)! + … + (n-1)! – n times
so n!;
T(n) = n!;
complexity theory – Configuration of a space bounded turing machine
A configuration of a turing machine is defined as the following:
an ordered triple (x, q, k) ∈ Σ∗ × K × N, where x denotes the string
on the tape, q denotes the machine’s current state, and k denotes the
position of the machine on the tape
I have read in a paper that a space bounded non-deterministic turing machine (NSPACE), has at most 2^(d*n) configurations on an input of length n, where d is a constant, how do we know that this is true? what is d? and how can we prove it?
Time complexity of a^{n^b}; a,b>1
What ist the running time of this expression? And how is it compared to factorial complexity O(n!)?
fast fourier transform – Complexity of a variant of FFT
To the best of my knowledge, FFT algorithm enables us to compute the matrix-vector multiplication $boldsymbol{Fx}$ with complexity of $O(Nlog N)$ where $boldsymbol{F}$ is a $Ntimes N$ Fourier matrix and $boldsymbol{x}$ is a length-$N$ vector. I’m thinking of a variant of FFT: only first-$k$ components of $boldsymbol{x}$ are nonzero. How much complexity can we save in this case?
Best regards,
Heedong Do
complexity theory – Create a turing machine for log base 2 of n
How would someone create a Turing machine that computes ⌈log2(n)⌉?
I know that:
n = 1, 2, 3, 4, 5, 6, 7, 8, …
f(n) = 0, 1, 2, 2, 3, 3, 3, 3, …
And that I want the input tape to have n 1’s in it to represent the number i.e. 8 would be
###11111111###
How would the the turing machine for this be created?
URGENT Recursive Complexity? – Computer Science Stack Exchange
Given the following question:
$T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$
Using a set of complicated equations I found and proved that $a=9/10$ is the correct answer (for sure)
My question is, how can I prove that $a>1/10$ as someone mentioned it’s too easy?
(Note: I’m not saying that 1/10 is the correct answer but rather asking for help proving a small side note)
complexity theory – Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$?
I thought they did, but recently I tried to express $3^n$ as $k times 2^n + o(2^n)$ for some constant $k$ but wasn’t able to. All I found was $3^n = (frac{3}{2})^n 2^n$. What am I misunderstanding here?
I suppose my question applies to $log_c(n) = O(log_2(n))$ as well.
complexity classes – What is the computational class of a pushdown automaton with real values?
Say there is a push-down automata, in this example I’ll use a deadfish-like set:
+: increase x by 1
0: set x to 0
ln: set x to ln(x) <-- real valued result
With x being an infinite precision real-valued variable, does this allow said machine to have more power than if it was operating on integers? Or am I misunderstanding something?
