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)

1
vote
1answer
44 views

Clarification over what NP means

I'm reading an informal definition of the decision class NP with a specific example being the standard knapsack problem and a decision variant of this problem. The example they are using is a ...
0
votes
0answers
14 views

Implications of deterministic Polynomial Identity Testing

It is well-known that polynomial identity testing (PIT) has a polynomial time Monte-Carlo algorithm. At the same time, no efficient deterministic algorithm is known. I came across a paper of Kabanets ...
0
votes
1answer
43 views

Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ [closed]

Suppose A is a arbitrary subset of Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ with respect to $ n \in A \Longleftrightarrow n \in A_n $ and $A_n$ is finte, which of them is True? a) A and ...
5
votes
4answers
95 views

What is the number of full binary trees of height less than $h$

Given a integer $h$ What is $N(h)$ the number of full binary trees of height less than $h$? For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't ...
0
votes
0answers
40 views

Kirchoff's First Law (Algorithm Complexity)

I want a help in understanding the figure and the complexity of Kirchoff's First Law Kirchoff's First Law states that the number of incoming flows into a node must be equal to the number of outgoing ...
0
votes
0answers
23 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
0
votes
0answers
32 views

Proof the Restricted Case of CVP is P-complete

Show that the following Restricted Case of CVP is P-complete: Like CVP, except the input circuit satisfying the following conditions: All gates are placed int layers; the inputs of a gate come from ...
0
votes
1answer
71 views

Finding the complement of a set by negating logical statements

As part of an exercise I've been given the assignment to find the complement of the following statement: L = {P⊆{0,1}*: P is a legal encoding of a C program, and P terminates on all but a finite set ...
0
votes
0answers
39 views

Do three valued basis vector elements lead to the fastest discrete Fourier transforms?

When sin() and cos() are approximated to 1, 0 and -1 in the basis vectors in a real or discrete Fourier transform the basis vectors have a lot of elements of zero or in common leading to an algorithm ...
0
votes
0answers
24 views

Notation in a fast perfect-power classification algorithm

I'm trying to implement a lengthy perfect-power classification algorithm with an interesting complexity of $O(\log_2(n)^{O(\sqrt{\log\log n\log\log\log n})}).$ To do so, I'm referring to Daniel J. ...
2
votes
1answer
137 views

the algorithm and computation cost for truncated SVD in rank k

It seems that the time cost of truncated SVD in rank k for matrix $A\in R^{m\times m}$ is $O(m^2 k)$. Could anyone show me some algorithms to calculate truncated SVD with the above time complexity?
1
vote
1answer
52 views

Formal definition of a set of graphs according to diameter restriction

I'm trying to find a formal way of defining the set of all directed graphs which their diameter is at most X, by formal definition I mean something of the following form: {G | G=(V,E) , G is a ...
1
vote
2answers
86 views

How to calculate the inverse of sum of a Kronecker product and a diagonal matrix

I want to calculate the inverse of a matrix of the form $S = (A\otimes B+C)$, where $A$ and $B$ are symetric and invertible, $C$ is a diagonal matrix with positive elements. Basically if the ...
0
votes
1answer
31 views

Computational complexity of Gauß-Seidel method

I'm currently studying iterative methods to solve equations of the form $Ax=b$ One method that is presented in my script is the Gauß-Seidel method where one step is defined as: $$x^{(k+1)} = ...
2
votes
1answer
84 views

Why are there no continued fraction representation for $\pi$ obeying mathematical rules?

There are several irrational numbers that can be represented with continued fraction such that a mathematical rule arises in this continued fraction. For example, the Euler number $e$ can be ...
2
votes
1answer
81 views

How to solve this logarithmic inequality?

I've started a data structure course and I need some help with solving these logarithmic inequalities. It would also be helpful because later on these kind of calculation won't pose a problem later ...
0
votes
2answers
52 views

Finding the biggest decrease in a list of integers (Python)

Given an array of n integers, h0, . . . , hn−1, I want to find the largest decrease in values such that the largest decrease is max(hi − hj) such that i ≤ j. For example, given as an input the array ...
0
votes
2answers
129 views

Computation complexity with simple algebra expression reduction

I'm watching this computer science video on computational time complexity of a function where they introduce some maths and it doesn't make sense to me. I'm not even sure what the name for this maths ...
1
vote
0answers
27 views

why some people use the notation $a \leq O(n)$?

When describing the algorithm complexity denoted by $c$, some people use $c \leq O(n)$ instead of $c =O(n)$ to show complexity. I cannot understand why they should use $\leq $?
0
votes
0answers
156 views

How to prove worst case time complexity for binary search

I have the following problem: Show that the worst case time complexity for Binary Search is given by: $W(n) = \lfloor lg(n) \rfloor + 1$ when n is not restricted to being a power of 2. ...
0
votes
0answers
31 views

How to find asymptotic cost of matrix filling algorithm . Big O Notation

So I have a list X of N strings each of length M that will be called x_i for the ith index in X Example ...
0
votes
1answer
46 views

How do we solve for $n$?

Asymptotic complexity gives an idea of how rapidly the space/time requirements grow as problem size increases. • Suppose we have a computing device that can execute 1000 complex operations per ...
0
votes
0answers
15 views

Lower bound for a difference

Let $x_1,\dots, x_n$ be $n$ positive real numbers. And $k$ be an integer with $k<n$ (in practice $n=k^2$ if it helps). I want to compute the smallest difference between the sum of two sets of $k$ ...
0
votes
0answers
38 views

Karatsuba's algorithm smart

I have a problem that I want to solve. I really tried but it does not budge. If the input is of size n for Karatsuba's algorithm We have three steps in Karatsuba's algorithm: 1) Recursively compute ...
0
votes
1answer
29 views

Big-O complexity of iterating over every substring

What is the Big-O complexity of iterating over every possible non-empty substring of a string of length $N$? The simple way to do the iteration over string $S$ is: ...
0
votes
1answer
14 views

Is CLIQUE PROBLEM polynomial on a class of graphs $\mathbb{G}$, if $\mathbb{G}$ has one graph.

By CLIQUE PROBLEM I mean whether $\omega(G) \geq k$ for $k \geq 3$. If $\mathbb{G}$ has just one graph, is the CLIQUE PROBLEM polynomial when restricted to $\mathbb{G}$? My Attempt: I can check ...
1
vote
1answer
37 views

Why do O(logn) & O(exp(n)) Have Polynomial & Non-Polynomial Running Time Complexities Respectively Despite Their Taylor Series?

I understand that a function, say $f(x)$, belongs to a class $O(g(x))$ iff: $$ \exists k > 0 \ \ \exists \ \forall n > n_0: |f(n)| \leq |g(n) \cdot k| $$ I also know that $log(x)$ is has ...
6
votes
2answers
254 views

Hamiltonian Weighted Graph and Decision Problems

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
1
vote
1answer
34 views

Theory of computation

For any language $A$, $B$ and $C$ such that $A\subseteq B \subseteq C$, if both $A$ and $C$ are decidable, then $B$ is decidable. True or False? How can I find this?
2
votes
1answer
33 views

Complexity class of conditional dependency resolution

I have a problem I am (considering) writing an algorithm for, but which I suspect to be NP-hard. However, I have not been able to prove that it is in fact NP-hard. The problem is stated as so: Given ...
3
votes
2answers
75 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
0
votes
1answer
137 views

How to evaluate growth of input size from n to 2n in this case?

This is the question I am currently working on What is the effect in time required to solve a problem when you double the size of the input from n to 2n, assuming that the number of milliseconds the ...
3
votes
1answer
42 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
0
votes
0answers
23 views

Shouldn't big oh definition be if and if only if, not just if? [duplicate]

This is from Discrete Mathematics and its Applications Shouldn't the if in that definition be an if and only if? Say we know that $n^2$ is in O($n^2$). Then from one side of the if and only if, we ...
0
votes
2answers
28 views

How to come up with an interval for this Big Oh Problem?

This is from Discrete Mathematics and its Applications I'am trying to use the interval method like what was shown in this example Here is my work so far: I noticed that when $x > 5$, $2^x > ...
1
vote
1answer
11 views

Factorization of sum and difference of factorized coprimes

If I have the prime factors of two coprimes $a$ and $b$, is it possible to find the prime factors of $a + b$ and $a - b$ faster than a full factorization?
0
votes
1answer
31 views

Construct a Turing Machine M' such that if M accepts a then M' accepts a and if M doesnot then M' does not halt

Give a TM $M$. Construct a Turing Machine $M'$ such that 1)if $M$ accepts $a$ then $M'$ accepts $a$ and 2)if $M$ does not accept then $M'$ does not halt. I am thinking about a 2-tape TM, with ...
30
votes
4answers
636 views

What is the *middle* digit of $3^{100000}$?

The decimal representation of $3^{100000}$ has $47713$ digits. What is the $23857^{th}$ digit - i.e. the one in the $10^{23856}$'s place? There are lots of questions on this site asking for the ...
3
votes
0answers
60 views

Category theory and complexity classes

Is there any interesting way to make the set of computational complexity classes into a category? Almost every interesting mathematical class of objects forms a category after all.
2
votes
1answer
56 views

Theory Of Computation - recognizable and decidable

How to prove that for any language $A$, if $A$ is recognizable and $A \leq_m A^\complement$, then $A$ is decidable. I know this theorem - A language is decidable iff both it and its complement are ...
0
votes
0answers
34 views

Computing a lower bound for the minimal componentwise distance of vertices of polyhedra

Let $A$ be a matrix in $\mathbb{R}^{m \times n}$ and let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a polytope. I want to compute a lower bound on the minimal componentwise distance of two ...
0
votes
1answer
45 views

Decision Problems and Poly Time

We have Two Decision Problem A and B. we know A is NP-Complete, but B can be solved in $O(n^2lg^4n)$, and we know $B \leq_pA $ (i.e each problem of B can be convert to a problem of A in Polynomial ...
1
vote
1answer
55 views

Asymptotic and 3-SAT problem in Algorithm Course

my TA says just one of the following is True, anyone could describe me some detail about following three lines? 1- if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then ...
0
votes
1answer
30 views

How may times should I colour a colour palette to have distinct colours?

Suppose that we have a colour palette, i.e., an array of n elements, which needs to be coloured by distinct numbers. We are only allowed to use 0 or 1 to colour every elements in each colouring step. ...
3
votes
1answer
60 views

Simple factorials

I've been doing some work with factorials and the normal way of calculating them is simply not working so well. When the numbers get really big, doing iterative multiplications is not viable and gets ...
0
votes
0answers
60 views

Best strategy for this archery-based probability game

This is with reference to the comments posted by @Trenin on my answer to this question. He says that since 2 players strategies depend on each other, we can't get the best strategy so easily. My ...
0
votes
1answer
50 views

How to give a big O estimate/visualize for these while loop?

This is from Discrete Mathematics and its applications I am currently working on problem 4. I was able to see that for problem 2, that one operation one will run n times for every n(meaning in ...
0
votes
1answer
25 views

Show the correctness: $\log^3( n)\in o(n^{0.5})$

show the correctness: $\log^3 (n)\in o(n^{0.5})$? I started from this way $$\log \log \log( n) = n^{0.5}$$ then I take $\log$ for two parties $$\log\log\log\log( n) = 0.5 \log( n)$$ ...
0
votes
0answers
41 views

How to show that $2^x$ is not in $O(x^2)$?

This is from Discrete Mathematics and its Applications I am working on 2e. I knew right off the bat from previous computer science courses that 2^x is not in O(x^2). I am having a difficult time ...
0
votes
0answers
29 views

Why can't this inequality hold true for all n > k?

This is from Discrete Mathematics and its Applications I am having trouble with why the "inequality n <= C cannot hold for all n with n >k". Is this reasoning for this that there is no largest ...