Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

What is the complexity of finding f-reducing polynomial?

For a finite field $\mathbb F_q$, where $q$ is a power of prime. I want to know that complexity of finding f-reducing polynomials. The following is a definition of "f-reducing polynomial" Def) If $h ...
0
votes
1answer
48 views

Master theorem for $T(n) = 9T(\frac{n}{3}) +4n^6$

based on master theorem, I arrived at $$n^{2} ,f(n)=4n^6$$. So is the answer $$\theta(4n^6)$$ or is it just $$\theta(n^6)$$. And also, can this be solved with substitution method?
0
votes
0answers
25 views

Complexity analysis of alpha beta pruning of a full tree

I am trying to understand the derivation of a time complexity for an alpha-beta pruning algorithm but up till now have not found any reasonable recourse. Many recourses claim that if you take a full ...
0
votes
0answers
40 views

How does this small change in the Pollard Rho method affect it's complexity?

The Pollard Rho method's complexity is O(sqrt(p)). Correct? Now let's say I tweak the method just a little bit and not actually check if |X_i-X_j| = p (or a multiple of p), but if it equals p - 2 (or ...
0
votes
1answer
17 views

How this complexity calculation

I'm not familiar with this complexity calculations. Someone could tell me how T(n) = T(n/2) + θ(1) become T(θ) = θ(log2 n) ...
0
votes
0answers
24 views

Fourier-Motzkin elimination number of constraints

I have this question: Consider Fourier-Motzkin elimination algorithm. Let n = 2^p+p+2, where p is non-negative integer. Consider a polyhedron in R^n defined by the m = 8(n 3) constraints. ...
0
votes
0answers
7 views

Trouble determining if these states are bisimilar

I know that for each state, for all s --a--> s' there must be a t--a--t' where t' = s'. But I'm unsure if s1, s2, and s3 are bisimilar due to the fact that s2 cannot match s1 and s3 because s1 and ...
0
votes
0answers
19 views

What is the complexity of comparing two #P-complete counts?

Given a counting problem with complexity #P-Complete and two inputs $X_1, X_2$, what is the complexity of deciding whether the count for $X_1$ is greater than, less than, or equal to the count for ...
1
vote
2answers
47 views

Calculate complexity for simple algorithm using summations

I want to calculate exact bounded complexity (theta) for the following simple loop system ...
0
votes
0answers
25 views

Define $T(2^n) = T(2^n/n) + 1$ with $T(1) = 1$ . Is $T(2^n)∈ Θ(n) ?$

I'm trying to solve the following problem $:$ Define $T(2^n) = T(2^n/n) + 1$ with $T(1) = 1$ . Is $T(2^n)∈ Θ(n) ?$ If I convert this recurrence relation into $:$ Define $T(k) = T(k/log_2k) ...
0
votes
0answers
74 views

What is the asymptotic complexity of?

$$T(n) = \begin{cases}T\left (n/\log_2{n}\right) + 1 & n>2\\1&n\leq 2\end{cases}$$ I'm tempted to think that the answer is $\Theta(\log n)$, but the denominator decreases as $n$ decreases. ...
0
votes
0answers
21 views

Concerning Big O Notation

I'm looking at a Time Complexity problem here and want to clarify something. If I have $n^2$ and $n^{2.5} \log^3 n$ I would most certainly say that this function is $\Theta(n^{2.5} \log ^3 n)$ ...
4
votes
2answers
970 views

Is Cramer's rule efficient for computational point of view?

I am not sure if Cramer's rule is used for computation purposes. Your help would mean a lot. Thanks!
1
vote
5answers
69 views

How does $\sqrt{2}^{\log n}$ become $n^{\log \sqrt{2}}$ [duplicate]

In proving that $(\sqrt2)^{\log n}$ = O(n)$, where log is base 2, the solution is below. I understand the solution except for the two lines that I starred. How does the first line become the second ...
1
vote
1answer
48 views

Counting number of loops

How many multiplications are performed when the following code fragment is executed? Express your answers in terms of $n$, where $n \geq 10$. ...
0
votes
2answers
45 views

Counting Iterations

How many multiplications are performed when the following code fragment is executed? Express your answers in terms of $n$, where $n \geq 10$. ...
-2
votes
2answers
95 views
0
votes
0answers
18 views

How can I solve a recurrence whose base case is not of size 1?

I am trying to solve the following recurrence function, but I am stuck since I don't think I can apply the Masters Theorem. B and M are predefined values (though not given), and $M>\Theta(B^2)$ ...
0
votes
1answer
121 views

Show that for any real constants a and b, where b > 0, (n + a) b = Θ(n b ).

Show that for any real constants a and b, where b > 0, $(n + a)^b = Θ(n^b)$. So taking a stab at this.. I let $a = 0$, and $b = 1$ So I got $f(n) = (n + a)^b \implies f(n) = (n+0)^1$ which we know ...
0
votes
2answers
180 views

Let f(n) and g(n) be asymptotically non-negative functions. Using the basic definition of

1. Let f(n) and g(n) be asymptotically non-negative functions. Using the basic definition of Θ-notation, prove that max{f(n), g(n)} = Θ(f(n) + g(n)) I'm not really quite sure what this question is ...
0
votes
1answer
54 views

In each of the following situations indicate whether…

In each of the following situations indicate whether f = O(g), or f = Ω(g), or both (in which case f = Θ(g)). $f(n) = n\log n, \\g(n) = 10n\log10n$ The solution is saying that both are $O(n\log n) ...
1
vote
2answers
22 views

Big O complexity of equation

Can someone explain how I wouldfigure out the big $O$ notation for this expression? $$n+(n-1)+(n-2)...+(n-(n-1))$$ My thoughts is that it's $\mathcal{O}(n)$ because I think of all the other terms ...
0
votes
0answers
12 views

Why $NSPACE(S(n)) \subseteq DSPACE(S(n)^2)$ and not vice versa?

Need to understand exactly why $NSPACE(S(n)) \subseteq DSPACE(S(n)^2)$ and not vice versa. Why we cannot say that $ DSPACE(S(n)^2) \subseteq NSPACE(S(n)) $ ? Thanks!
0
votes
1answer
24 views

How do I convert integer to an n-tuple, given that I know how the integer was computed?

I have an integer n, and a 6-tuple: (a,b,c,d,e,f). Each element of the tuple has a range: ...
1
vote
3answers
54 views

What's the difference between $t(n^2)$ and $t^2(n)$

Theorem: For every multitape Turing Machine algorithm that takes time $t(n)$, there is an equivalent single tape Turing Machine that takes time $t^2(n)$ I am curious why we say $t^2(n)$ and not ...
0
votes
1answer
42 views

Can every problem in P be polynomially reduced to every other problem in P?

If A and B are in P and A can be polynomially reduced to B. Then can B be polynomially reduced to A? If yes then how? Another way to think about it. If A is NP-complete and B is in P and if A can ...
0
votes
0answers
28 views

For what functions ($T_1, T_2: N \to N$) there is oracle B and language $L=L_b$ that $L \in ND-TIME(T_2)^B$ but $L \notin TIME(T_1)^B$

I had this question: For what functions ($T_1, T_2: N \to N$) there is oracle B and language $L=L_b$ that $L \in ND-TIME(T_2)^B$ but $L \notin TIME(T_1)^B$ Only one answer is the correct one: A. ...
0
votes
1answer
27 views

Can somebody explain what inclusions of complexity classes (such as $DTIME$ or $DSPACE$) mean?

I am trying to understand what book is saying: Let $S(n) \leq log(n). Then$ $$DTIME(T(n)) \subseteq DSPACE(T(n))$$ $$NTIME(T(n)) \subseteq NSPACE(T(n))$$ $$DSPACE(S(n)) \subseteq ...
1
vote
1answer
36 views

Composition of Functions with Big-Oh

I'm in the process of learning Big-Oh and came across an equality presented as a fact without justification: $\sqrt{n + \mathcal O(n^2)} = \sqrt{n} + \mathcal O(n^\frac{3}{2})$ Is this so? What is ...
0
votes
0answers
40 views

Prove these problems are polynomial time equivalent.

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$. ...
1
vote
3answers
126 views

How to prove that n! have a higher order of growth than n^(log n)?

I am aware that n^n have a higher order of growth than n!, but how about n^(log n)? Is there a way to get an alternative form of n^(log n) such that when taking the lim n to infinity [alternative ...
2
votes
1answer
25 views

Do these functions have the same order of growth?

I have a list of functions and was confused whether they have the same order of growth. $$f(n) = \Theta(g(n))$$ Given functions: $\log^2 n, \log(n^2) $ My method: I took the logs of both functions ...
0
votes
0answers
30 views

Reducing computational complexity of an exhaustive search

In a paper I have come across an algorithm that claims to reduce time search of an another exhaustive algorithm. Both alrogithms are searching for maximum value. I will not go through the details of ...
0
votes
0answers
30 views

NP-hardness of CIRCUIT-SAT

How to prove NP-hardness of CIRCUIT-SAT, without the use of other NP-complete problems but using Turing machines? And, if it is possible, I need a full proof, not a sketch.
0
votes
0answers
64 views

NP hard to NP or P type problem

I am designing a security protocol and to protect my system from DDoS attack. To achieve this I need to define a problem with following characteristics: If the Problem has any unique input from set ...
-2
votes
1answer
27 views

can't solve this recurrence, please help [closed]

Give a closed form for this: T(1) = 1 T(N) = T(n/2) + log(n) Anyone can show me how to solve this?
0
votes
0answers
13 views

Question regarding $P\subseteq P_\textrm{/poly}$

In the proof of Complexity theory, a modern approach" by Boaz Barak and Sanjeev Arora they prove that $P\subseteq P_\textrm{/poly}$. In the proof they use oblivious turing machines (machines whose ...
0
votes
0answers
43 views

is the language $\{0\}$ P-complete?

How could you prove that the language $\{0\}$ is P-complete ? Can you please explain me in simple words ?
0
votes
1answer
55 views

Horner's Polynomial Evaluation for a postive and negative x

Solving a polynomial with value $x$ using Horner's method seems to use the least amount of multiplications and additions, 1 of each per pass. How would you use this with $\pm x$ using only $n + 1$ ...
0
votes
1answer
71 views

Computing the volume of intersection between a tetrahedron and a hexahedron.

I am trying to compute the volume of two intersecting objects in 3D. One is a tetrahedron and the other is a hexahedron. I just need the volume but it looks like I will have to find the polyhedron ...
0
votes
2answers
63 views

Does $O(n\cdot n!) = O(n!)$?

Does $O(n\cdot n!) = O(n!)$? I know that $n*n! < (n+1)!$, and in Big Oh we usually throw out constants, so it seems like we could make this conclusion. However I am not sure how to show this ...
1
vote
0answers
47 views

Arrange in ascending order of complexity [closed]

1) $n$ and $n\log\log n$ 2) $n^2$ and $0.001n^3 + 2000n$ I am having a hard time understanding what complexity means.
0
votes
0answers
36 views

Worst case complexity of Shell Sort

I am considering the gap sequence $g=4,2,1$. I am able to prove that the upper bound of the algorithm is $O(n)$ assuming that in every step we are going to have $g$ insertion sorts of $n/g$ elements ...
3
votes
1answer
139 views

Fooling set method

In the book Computational Complexity (By Sanjeev Arora and Boaz Barak) a method called "The fooling set" is mentioned, when trying to bound the communication complexity of a function from below. A ...
1
vote
1answer
28 views

sum or polynomial of a polynomial?

I am trying to answer the following math problem but I barely understand the question. If $P(i)$ is a polynomial of degree $d$ in $i$ then $\sum\limits_{i=0}^n p(i)$ is a polynomial of $d + 1$ in ...
0
votes
0answers
12 views

BPP=P question game theory

Imagine a computer that simulates games of 2 players where it is advantageous to make random moves. If BPP=P, does this mean such a computer would not need any random inputs, yet to an outsider ...
2
votes
1answer
107 views

Minimally Good Sequences

Let $k$ be a fixed positive integer. Let a sequence of positive integers with odd sum $(a_1,\ldots,a_n)$ be called good if for all integers $1 \leq i \leq n$, we have $\sum_{j \neq i} a_j \geq k$ Now ...
0
votes
0answers
35 views

Bijection between tensors and permutations (in linear $O(n)$ time)

The number of permutations of the set $S=\{1, \dots, n\}$ is $n!$, or in other words the permutation group $S_n$ has $n!$ elements The number of tensor components of a tensor in $n$ dimensions ...
0
votes
1answer
21 views

Calculate difference in throughput between two computers when the time complexity is $2^n$

The time complexity for some algorithm is $T(n) = 2^n$ where n is the size of inputs. A particular computer takes t seconds to process n inputs. How many inputs can a computer that is 64 times as fast ...