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)

2
votes
0answers
14 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
-7
votes
0answers
26 views

What would happen IF [on hold]

If someone, sometime put prime factorisation in P by finding some new approach. An obvious direct consequence would be cryptographic issues with keys exchanges.... that could lead to some economic ...
0
votes
1answer
17 views

Prove that $ (lg\; lg\; n)^k=o(lg^\epsilon n)$ for all $0<k,\epsilon$

I am stuck at this problem for a long time: Prove that $ (lg\; lg\; n)^k=o(lg^\epsilon n)$ for all $0<k,\epsilon$ I tried to show that $\lim_{x\to\infty}\frac{ (lg\; lg\; x)^k}{lg^\epsilon ...
-2
votes
2answers
72 views

What is the algorithm to add 2 binary with boolean operations? [on hold]

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
0
votes
1answer
22 views

what is the complexity of this type of algorithms (loop bounded)?

I have an algorithm which contains only the instructions of type: $X_i=X_j$ $X_i=X_i+1$ $\text{while }(X_i\le N)\text{ do }\{C\}$ where $C$ is another instruction $N$ is a global constant and ...
2
votes
1answer
42 views

Why is Chaitin's constant absolutely normal?

I have repeadetly seen claims that Chaitin's constant is normal in all bases (e.g. on Wikipedia), and I have also seen some proof sketches (e.g. here), but these only show the idea. For example, the ...
0
votes
2answers
41 views

Clarification on the big oh of the sum of two functions

In computing the asymptotic complexity of the sum of two functions, one theorem states that if $\large\lim_{n\rightarrow\infty}\frac{f_2(n)}{f_1(n)}$ exists, then the asymptotic complexity is ...
0
votes
1answer
299 views

What will be the time complexity of insertion if a queue is implemented using two stacks?

A Queue could be implemented using two Stacks. So what will be the time complexity for insertion and deletion in this queue? Thanks in advance.
1
vote
1answer
35 views

Minimize the squared dot product of two specific vectors

Do you think there exists a efficient algorithm(non brute-force) for the following problem. I search the optimal solution for the following problem: Given a vector $u=(u_1, u_2,..., u_k)^T$ with ...
0
votes
1answer
33 views

improved segmented sieve of erastothenes complexity

I improved the segmented sieve of erastothenes , my algorithm doesnt repeat the multiples of primes using the equation $p^{2}_{n}p_{j}+2p_{n}p_{j} \times c =N$ wich shows when at least two multiples ...
1
vote
0answers
15 views

Traversing multi-way tree, computational complexity

This is a computational challenge. I am looking for a clever simplification or heuristic. Imagine a multi-way tree. Each node has three child branches. Consider them to be decisions; do A, do B, do ...
0
votes
0answers
51 views

Finding an optimal substring in a string with the given pattern [on hold]

Suppose, we are given a set of variables $x_1, ... ,x_m$ with the levels $A, B, C, ...$. So, for instance, the $A$-level of the variable $x_i$ will be denoted as $A_i$, and we will call it a value. We ...
0
votes
0answers
42 views

Can you decouple the Traveling Salesman Problem from the number of cities?

I am studying the euclidian version of the Travelling Sales Man problem: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits ...
0
votes
2answers
178 views

Subset sum problem performance and benchmark

Looking for information about this topic (P vs. NP / Subset sum problem) I found next sample problem http://www.cs.utsa.edu/~wagner/CS3343/ss/ss.html Above URL contains a set of 100 integer values ...
2
votes
0answers
27 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
1answer
51 views

an strange set $ \Xi_A =$ {$ n \in N | \exists k^2 \in A $ s.t $ k^2 \leq n$} is decidable ?, an Interview questions?

We are some student that had an Interview for M.sc Entrance Exam. This interview has two part and one multiple choice question. We see 1 strange question that some definition is so strange for us, we ...
0
votes
0answers
45 views

Best time complexity for calculating the next, unique graph.

Whats the best time complexity, for a known algorithm, that when called generates the next, unique, graph, in order of node count? For example, the first result being the only single node graph, I ...
0
votes
0answers
16 views

Trying to determine the relationship of m and n in a Casting Out m under base n

While exploring $\mathbb{Z/n}$ I stumbled upon this It explains that Casting Out Nines works because our common counting system is decimal and thus there exist a congruence relation as follows ...
2
votes
2answers
76 views

P vs NP - examples of P and NP

I'm currently studying 'p versus np'. Can someone help me in showing an example of a mathematical p problem and np problem? A clear worked example would be much appreciated. Many thanks in advance.
1
vote
1answer
11 views

Reducing a problem X to an np-complete problem Y.

Say I have a problem X that I can reduce to an NP-complete problem Y. Can I assume that problem X is in NP? Can it not be in NP?
1
vote
0answers
27 views

How would you prove this Big Omega complexity?

We're given $f(n)=\frac{1}{5}n^2-30n-5$ and $g(n)=n^2$, and are asked to prove $f \in \Omega(g)$. The exercise was posted, but no solution is given (this is not an assignment question). So by ...
0
votes
1answer
37 views

On average, as a function of n, how many print statements are executed by the following algorithm?

On average, as a function of n, how many print statements are executed by the following algorithm? ...
7
votes
1answer
906 views

If an unary language exists in NPC then P=NP

I've a question regarding a theorem in Complexity Theory. It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct. It means that there exists ...
2
votes
2answers
12k views

What is the 3SAT problem?

I don't get the 3SAT problem. Can someone explain the 3SAT problem as if I were 5 years old, ideally with examples? Thanks!
4
votes
1answer
76 views

Computing the order of a group element

This is a partially computer theoretic question, but is probably closer to math. I remember finding a paper from 1980's or so that had a proof of the fact that finding the order of a group element is ...
0
votes
1answer
55 views

Better time complexity.

I am new to complexity theory and want to know, Which one is better time complexity(faster) for an algorithm ? \begin{equation} \frac{n^{k+\log_2(n)}}{\log_2(n)2^{n}} \end{equation} or ...
1
vote
1answer
38 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
7 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
39 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
59 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
27 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
18 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
1answer
28 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
13 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 ...
1
vote
1answer
133 views

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$. A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} ...
0
votes
0answers
25 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 ...
1
vote
1answer
34 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
45 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
0answers
17 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. ...
1
vote
0answers
44 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?
2
votes
1answer
60 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
1answer
16 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
73 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 ...
0
votes
2answers
40 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
1answer
51 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
22 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
56 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
12 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
43 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 ...
7
votes
2answers
247 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 ...