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
26 views

Hamiltonian path problem vs other NPC problems

If we can solve the Hamiltonian path in time $O(n^4)$ then you can solve any other NPC problem in $O(n^4)$ time. Is it true of false? I think it is false, even tho Hamiltonian path problem in NPC it ...
0
votes
1answer
381 views

checking boolean logical equivalence

Given two boolean formula (aka. logic circuit), I want to check if they are logically equivalent, namely that they compute the same truth table. Is this an NP-complete problem? What is the proof?
0
votes
2answers
55 views

prove that a polynomial is lower bounded

I need help with this question from Data-Structure course. I need to prove that the following polynomial is lower bounded by $n^k $, meaning I need to show that: $$ p(n) = b_kn^k - ...
1
vote
1answer
59 views

Factoring semiprimes cost estimation

I have two problems that are the following. The first problem is the following: I need to estimate the cost of factorizing a given semiprime based on previous estimations. For example I have the time ...
0
votes
0answers
7 views

Algorithmic complexity from knowing complexity due to two different factors.

I have an algorithm that has complexity depending on two factors $n$ and $m$. If I know that fixing $m$ I have complexity $\mathcal{O}(n^p)$ and fixing $n$ I have complexity $\mathcal{O}(m^q)$, can I ...
1
vote
1answer
77 views

Computational complexity of solving linear diophantine equations?

Is there any good complexity upper bound for checking satisfiability of a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$? I found some estimate on computing the Smith Normal Form $N$ such that ...
3
votes
1answer
72 views
+50

Solving the Gobblet game

In 1995 the Connect-4 Game was solved with a brute force approach. Using the standard 6 high / 7 wide grid, first player can force a win in 41 moves. Complexity of the Connect-4 game could be ...
1
vote
1answer
443 views

Computational complexity of Gaussian elimination

If it took me approximately 4 minutes to solve an equatian $Ax=b$ for $x$ (where $A$ is a $3\times3$ matrix and $b$ is a $3\times1$ matrix) using Gaussian elimination, how much longer would it take me ...
0
votes
1answer
24 views

What will happen if any language in NP ∩ co-NP will become NP-complete?

I approached this question like this: Let B ∈ NP ∩ co-NP and B is also NP-complete. Then any other problem in NP can be reduced to B. Now take A ∈ co-NP. Then ~A ∈ NP which can be reduced in ...
1
vote
1answer
21 views

Omitting the refference to a particular logarithmic base - order notation

How can I prove by using the Order notation definition that we can conventionally refer to an algorithm taking "log time", without referring to a particular logarithmic base?
-1
votes
0answers
28 views

Time complexity of $T(n)=2^nT(n/2)+n^n$ and $T(n)=\sqrt{2n}T(\sqrt{2n})+n^2$? [closed]

What is the time complexity of : $$T(n)=2^nT(n/2)+n^n$$ and $$T(n)=\sqrt{2n}T(\sqrt{2n})+n^2$$
1
vote
0answers
14 views

Is $O(x^2)$ equal to OR a tighter bound for $O(x(x-y))$ if $x, y >0$ and $x>y$ alway hold?

In the question, $O$ is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. $x$ and $y$ are variables. Here, let me give you an example showing there exist such questions in ...
0
votes
1answer
20 views

complexity of $\ {n \choose n/3}$

I know that the complexity of this combination $\ {n \choose n/3}$ is of $\theta(n^{n/3})$ , but I'm in need of help proving it.
0
votes
0answers
18 views

Help me to find mixed chinese postman problem (MCPP) complexity

I know that MCPP is NP-Complete. Also, I have problem formulation: Chinese postman problem for mixed graphs. I was given a task to evaluate the number of operations required for a complete re-election ...
0
votes
3answers
39 views

Sieve of Eratosthenes Time Complexity Clarification

I've found plenty of sources claiming that the time complexity of the prime sieving algorithm Sieve of Eratosthenes is $O(n\log(\log n))$ where $n$ is the input. However, is this $\log_{10}$ or $\ln$? ...
0
votes
1answer
33 views

Big O for factorials

Hello I have trouble proving:$$(n+1)!\notin O(n!)$$ My first step is the following: $$(n+1)!-cn!\le0$$ Can you please help me with the next step?
2
votes
2answers
20 views

What does $\mathbb{Z}[X]$ for a polynom mean?

I have a proof saying that a Polynom $p \in \mathbb{Z}[X_1,...,X_m]$ I'm a bit confused of this notation because neither X nor the m is explains somewhere. Does somebody of you know the notation?
0
votes
0answers
10 views

Time taken to run a function R(n,a)

R(n, a){ if n = 1 return(a); if n > 1 return (R(n − 1) + R(n − 1) + 1); } Could you please explain me why the estimated time taken to run R(n, a) as a function of n is: (2^(n−1))*(a + 1) − 1 ? ...
0
votes
0answers
23 views

How can I solve this Big O exercise?

How can I prove that n log2(n) ∈ O(log(n!)) is true? We start by supposing that f(n)< c* g(n) is true, which means that n log2(n) > c*log(n!) for all n>n0 and c>0.
0
votes
1answer
430 views

How do I prove an algorithm has $n^3$ time complexity?

Take the CYK algorithm outlined here: How to prove CYK algorithm has $O(n^3)$ running time In the top answer, how did that person go from the three summations to $t=(n^3−n)/6$ ? What's the method ...
1
vote
1answer
56 views

Time Complexity of Sorting Algorithm

Here's my question: Analyze the runtime of the following algorithm. Will it successfully sort array S of n elements with values from 0 to m-1? ...
0
votes
2answers
44 views

What is the Order (Big O) of this polynomial?

$$\frac{2n^{14} + 7 n^8 - 3}{3n^8 - n^4 + 3}$$ If this division is $p(n)$, I have to write $p(n) = O(n^k)$ I guess the answer is $n^6$, but how can i solve it step by step?
0
votes
0answers
18 views

Turing Machine problem for unary division

How do I design a turing machine for this? Divide a given number by two in the unary number system.The quotient and the remainder should be written on the tape separated by a blank.
-1
votes
1answer
31 views

Prove little-o example

Let $f(x)=\log x$, and $g(x)=x^i$, where $0<i<1$. How can I correctly proof that $f(x)=o(g(x))$? Try 1: By the definition of little-o, a function is little-o of other function if $|f(x)|\leq ...
2
votes
1answer
23 views

How to prove that $f(x)$ is $O(x^i)$ for a general polynomial

Let $f(x)=a_ix^i + a_{i-1}x^{i-1} + \ldots + a_0$ where $a_i>0$. How can I proof that this general polynomial with real coeficients is $O(x^i)$ using the Big-O notation theory. Try 1: I thought ...
1
vote
0answers
33 views

Practical example of superiority of randomized algorithm

I'm looking for an example to show my students of an algorithm for which randomization of some kind leads to better performance on average. And I don't want that randomization to be of the Monte Carlo ...
0
votes
0answers
6 views

Graham's Scan Polar coordinates

I have this set of six cartesian coordinates and i need to sort them in order to apply Graham's. But i can't figure out how to do that. P[0] = (1,1) , P[1] = (2,6), P[2] = (3,3), P[3] = (4, 2), P[4] = ...
-1
votes
0answers
9 views

Pratical example of Theorem 1 in “Complexity of coalition structure generation” Article

Could someone help me to understand better, using some pratical example, the Theorem 1 in: http://oai.cwi.nl/oai/asset/18649/18649A.pdf I couldn't visualize by myself the abstraction being solved ...
10
votes
3answers
205 views

What is the most efficient algorithm for factorisation when an approximate value of one factor is known

If I am given the following number: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350 692006139 And am told that one of ...
0
votes
1answer
13 views

relations between Lower bound of 2 algorithems

I am given two algorithms A and B, with worst time complexity $$ f_A (n) $$ and $$f_B (n)$$ Respectively.Now it is given that: For each n there exists and input x of size n such that the number ...
0
votes
0answers
13 views

How we can compute complexity of algorithms in general?

I want to know how compute the complexity of below algorithm : Let $N$ be a positive integer that we don't know it's decomposition. Let $N$ has divisor $b$ such that $b\geq N^\beta$ , $0\leq \beta ...
5
votes
1answer
67 views

Minimal Elements with respect to big Oh

Let $\mathcal{F}$ be a finite set of functions from the natural numbers to the natural numbers. Consider the set $S_{\mathcal{F}}=\{g:\mathbb{N}\to\mathbb{N}\mid f\in O(g)\text{ for every } ...
1
vote
1answer
413 views

Solving recurrence relation: $ f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$

$f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$ I have attempted to solve it by letting $n = 2^k$ $f(2^k) = 3f(2^{k-1}) - 2f(2^{k-2})$ Then set $S(k) = f(2^k)$ $S(k) = ...
1
vote
1answer
36 views

MATLAB “back slash” computation [closed]

I am looking at a MATLAB code that times the backslash operator for several cases. I will list the cases below: Note: all of these are for m = 5000 1) Z = randn(m,m); A = Z'*Z; b = randn(m,1); tic; ...
2
votes
1answer
99 views

Euclid's algorithm and Gaussian elimination: most computationally efficient approach

I think this is more a mathematics question than a computer science one - but as it is about computational complexity it could be either, so apologies if you think it is in the wrong place... The ...
5
votes
2answers
66 views

At what point does exponential growth dominate polynomial growth?

It's well-known that exponential growth eventually overtakes polynomial growth (link, link). So for any non-negative integer $d$ and positive $\epsilon$, there exists $t^* \ge 0$ for which $$ 1 + ...
0
votes
0answers
22 views

Looking for info on representation of a diophantine equation as system of equations over finite field/boolean algebra

Suppose that $x$ is a positive integer. Fix some prime $p$. Then there exists some non-negative integer, $L$, and $\{x_0, x_1, . . . , x_L\} \subseteq \{0,1,...,p-1\}$ such that, $$x = ...
2
votes
2answers
38 views

How many arithematic operations(flops) are to $n×(n+1)$ matrix of system?

Source: Linear Algebra and Its Applications David C. Lay A system of n equations in n unknows correspond to $n×(n+1)$ augmented matrix. One book says the reduction(elimination) to echelon form ...
0
votes
0answers
15 views

Hardness of approximation for linear equations

Given a system of linear equations in n variables with coeffcients that are rational numbers, determine the largest subset of equations that are simultaneously satisable. Show that there is a ...
2
votes
0answers
39 views

Fast algorithm to recognize sortable sequences

Every sequence is sortable in the worst-case by a $O(n^2)$. However, if we restrict sorting primitive, we get an interesting problem. I am interested in this sorting problem: Input: a sequence $A$ of ...
0
votes
0answers
44 views

Good books on Algorithms for a math major without any programming experience?

I couldn't find this question anywhere else so it may not be apt. I am an undergraduate mathematics major and during my discrete math class I really enjoyed the study of algorithms and recursive ...
0
votes
4answers
41 views

Prove that an upper bound is incorrect

Probably a simple question that I cant figure out from data structure course: I need to disprove the following statement: $$ 8n^3 + 12n + 3\log^3n \ge n^4 $$ Now I know that from some value ...
0
votes
0answers
13 views

(Complexity) Subset of set of premises and the entailment problem

I've a finite set of propositional formulas $\Gamma$ and a logical conclusion $\psi$ over variables $X$. The following decision problem arises: Does a cosistent subset $\Gamma' \subseteq \Gamma$ exist ...
-3
votes
0answers
38 views

Complexity of computing the coefficients of the Newton interpolating polynomial

Could you help me solve this problem? Thank you very much for your help. Prove that the algorithm for computing the coefficients $c_i$ in the Newton from of the interpolating polynomial involves ...
0
votes
0answers
21 views

Determine number of vertex in a graph

I'm trying to determine the number of vertex in a graph $G=(V,H)$ where: $\displaystyle V = \left\{ v = (x_1, x_2, x_3) \in \mathbb{Z}_p^3:\sum_{i=1}^3x_i\equiv0\right\}$ with $p \ge 3$. Equivalent ...
-1
votes
0answers
26 views

Proof of concept using Shellsort algorithm

I have used the Shellsort algorithm in my experiment, where the purpose of the experiment is to demonstrate the useful use of Shellsort algorithm to detect a certain behavior on a giving data file, ...
0
votes
0answers
10 views

Does ray tracing have any speed ups in algorithm running time in the frequency domain?

Could ray tracing be Fourier-transformed so that all calculations are done in the frequency domain? I think ray-tracing a set of rays $S$ from the eye into the view frustum might be more efficient ...
0
votes
1answer
27 views

Can we extend NP-HARD proof of one problem to another?

I have tried to put my question in following diagram I have two domains A and B. I can formulate two optimizations problems 1 and 2. In domain A, efficient algorithms exist for solving these two ...
1
vote
1answer
17 views

Find a function f(n) such that T(n) is $\Theta(n \cdot log(n)) $

Find a function f(n) such that $ T(n)=16 \cdot T(\frac{n}{4}) + f(n) = \Theta(n \cdot log(n)) $ Also, another section of the question is where $T(n) = \Theta(n^{2})$ I've tried using the master ...
0
votes
0answers
20 views

Parallel Computing Mathematical Question (Amdahl's Law)

I have the following question, and I'm not even sure how to start this: A serial program takes T (e.g. ) hours to complete its execution. Assuming that the interprocess communication in a parallel ...