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

NDTM vs DTM running time of a program

I've found the following statement: If a program $P$ for Non Deterministic Turing Machine solves a decision problem in time limited by a polynomial $p(S)$, where $S$-size of input, then it can be run ...
1
vote
1answer
13 views

Is there a typo in this runtime analysis of selection sort?

This is from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf, slide 6. The instructor is doing a runtime analysis of selection sort. Here is ...
0
votes
2answers
15 views

Finding $2m+1=2\alpha k+\alpha^2$ quickly

Given some positive integer $m$ I'm looking for all solutions $\alpha,k>0$ to $2m+1=2\alpha k+\alpha^2$ with $0<k^2<2m.$ Right now I'm finding these by looping over each of these possible $k$ ...
1
vote
3answers
17 views

Recurrence Relations Closed Form

So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$ $\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 ...
0
votes
1answer
11 views

Using limits to prove a function is in the order of another function

I have to prove the following theorem: I am not asking for the whole problem, but am stuck on the first part (Proving that output of c implies g(n) is in the order of f(n)). I know the following: ...
0
votes
1answer
21 views

Big Omega problem : is $n^2\in\Omega (2n^2)$?

Is $n^2\in\Omega (2n^2)$? If we find the limit we can see $\frac{1}{2}>0$, which means it is true, but I haven't learned the limit method. I need to figure out using this definition $\exists ...
0
votes
0answers
23 views

Let g and h be any functions from naturals to (0,infinity)

Let $g$ and $h$ be any functions $\mathbb{N} \to (0,\infty)$. Then $g(n) \in \Omega(h(n))$ implies there is some $N \in \mathbb{N}$ such that $g(n)\ge h(n)$ for all $n \ge N$. Picture of question : ...
0
votes
0answers
15 views

How to calculate recurrence $F(n) = F(n/u) + \Theta(n^k)$ where $u,k \in \mathbb{N}$

$\Theta$ is used as in Bachmann-Landau notation (often called as Big-O notation convention). How does one in general the recurrence relation of the following from: $$F(n) = F(n/u) + \Theta(n^k) ...
2
votes
0answers
28 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
2
votes
0answers
33 views

$T(n) = 2T\left(\frac{\log n}{2}\right)+ \theta(n)$ [closed]

$T(n) = 2T\left(\frac{\log n}{2}\right) + \theta(n)$ can this be further simplified to a single asymptotic form? For starter, can I say that the answer is bounded by O(n) ?
1
vote
0answers
14 views

How to prove a language is NP-Complete where L consists of graphs (G,s,t) with a hamiltonian path from s to t [closed]

L = { (G,s,t) | G is a directed graph, a Hamiltonian path exists from s to t, and some path from t to s exists - (not necessarily Hamiltonian path) } How to prove L is NP-Complete ?
0
votes
1answer
63 views

Find roots of $ω^x+(ω^x)^2+1=x$ [closed]

We have to solve this equation at complex numbers group $ω^x+ω^{2x}+1=x$ I tried to find the roots, which led to $x = 0 , 3 $ But $0$ isn't right
0
votes
1answer
25 views

Solving a summation where the inner summation is limited by the iterator of the two outer summations

I'm trying to solve the following summation (where C is some constant) but I'm stuck because of the inner most summation which is limited by $i\sqrt[2]{j}$ where i and j are the iterators of the outer ...
-1
votes
1answer
26 views

Number of submatrices of sum K

I have an array $A[]$ of N elements ($N<=1000$, $-1000<=A[i]<=1000$). We define a Matrix M such that $M[i,j]= A[i]*A[j]$. In the resulting matrix $M$, we have to count the number of ...
0
votes
0answers
9 views

(Un-)Decidability of the isomorphism/classification problem for complex manifolds

It is easy to find references for the undecidability of the question whether two (smooth) real manifolds are diffeomorphic and/or homotopy equivalent. One can even say that given a manifold $M$ it is ...
2
votes
0answers
39 views

Book or paper recommendation about “Rube Goldberg Mathematics” // e.g. Longest path problems

First: My question is not be very specific, since I lack a concrete overview, but my idea/thoughts in a nutshell: I would like to have a recommendation of a good book, paper or article about processes ...
1
vote
0answers
24 views

When does $A,A\cap B, A\cup B\in S$ imply $B\in S$?

Let $S\subset 2^{\Sigma^*}$ be some family of formal languages over some alphabet $\Sigma$. Consider the the following statement: $A,A\cap B, A\cup B\in S$ implies $B\in S$ For which ...
1
vote
1answer
36 views

Determining the coefficient of $x^n$ in $\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$

I looking for an algorithm to efficiently find the value$\mod p$ of the coefficient of $x^n$ in a generating function of this form: $$\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$$ where $p$ is some prime ...
1
vote
1answer
11 views

some notations in algorithm analysis

Assuming $k$ is a variable, 1.then someone claims that the algorithm complexity is super-linear or sub-linear in $k$, here what is the meaning by using super-linear or sub-linear? 2.also, if ...
3
votes
0answers
17 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...
2
votes
0answers
34 views

how to count possible planar bipartitions?

i want to find out what small fraction of a solution space a metaheuristic search is actually covering. this case comes down to the number of possible bipartitions for a non-bipartite, undirected ...
3
votes
1answer
73 views

Applications of computer science to mathematics

I have been introduced to algorithms, computability and computational complexity (as part of my minor in CS). What are some mathematical topics that I can tackle with the new perspectives I ...
0
votes
0answers
18 views

Is this variant of the Stable Roommate problem NP-hard?

I want to organize $2n$ people ${A, B, C, \dots}$ in pairs. Each people rates every other one with an integer number going from 0 to 10. The ratings may not be reciprocal (i.e., A may rate B a 10, and ...
0
votes
0answers
39 views

Conjectured optimal running time for integer factorization

While detecting prime numbers is computationally fast ($O(\log^3 n)$), the fastest known algorithms to split a composite number into its prime factor are very slow (RSA cryptography relies on this ...
0
votes
1answer
24 views

Complexity of polynomial simplification into standard form

I am curious to know if any given $n$-variable polynomial in $\mathbb{R}[\mathbf{x}]$, not in standard form, can be simplified by an algorithm in polynomial time. The polynomial is $$ p(\mathbf{x}) = ...
0
votes
1answer
26 views

Complexity of factoring integers by trial division

Ok, I have a real problem with understand the complexity of this algorithm: set k=n; while k!=1{ while True{ d=k/i; if type(d)=integer{ i is a factor; break; } } } So we go through the internal while ...
0
votes
0answers
37 views

How to pronounce the complexity of an algorithm

I have a few questions regarding complexity: How do you name this complexity: $ f(M,D) = O(M^D) $. Is it f is exponential in D and what exactly in M, polynomial? Just to confirm $ f(M,D) = O(MD)$ is ...
1
vote
0answers
31 views

Is it better to compute $A^tA$ once and then $Ax$ several times or compute $y=Ax$ and then $A^ty$ every time?

So I have this algorithm which given a matrix $A$ it assigns $A=A^tA$ outside the loop and then on the algorithm loop it solves multiple instances of $Ax$ for different $x$s, (meaning that it's ...
1
vote
1answer
22 views

Getting tight asymptotic upper and lower bounds of product logs

Consider $$ E(n)=\log_2\left(\log_2 (4)\right) +\log_2\left(\log_2 (5)\right) ... \log_2\left(\log_2 (n)\right) $$ This is equal to $$E(n)= \log_2\left(\log_2 (4)*\log_2(5)*\log_2(6) ... ...
1
vote
1answer
28 views

Finding sparsest solution of a linear system

I want to find the solution $x$ with most zeros in its components, to: $Ax=b$ for $A\in \mathbb{R}^{k \times n}, b \in \mathbb{R}^k$ ($k < n$), where $x \in \mathbb{R}^n$ has no additional ...
2
votes
1answer
26 views

Can a halting turing machine write any combination on a tape before halting?

Assume, a halting turing machine uses $n$ items of the tape. Can it write every possible combination on this $n$ items before halting ? We start with a blank tape. Example $n=2$ , alphabet $0,1$ ...
5
votes
1answer
41 views

Can PA prove very fast growing functions to be total?

The Goodstein-sequence is a total function, but PA cannot prove this. Is this true for any other function with growth rate at least $f_{\epsilon_0}$ or are there functions growing at least as fast ...
0
votes
2answers
22 views

complexity of equivalence of two star-free regular expressions

Given regular expressions s,t that do not contain the Kleene star $.^*$, what is the complexity of deciding whether they define the same language? I am sure this can be done in NP-time; but is it ...
1
vote
1answer
33 views

$ f(n)=2\log(n)+\frac{n}{2} $. Find $g(n)$ so that $f(n)=O(n)$

$ f(n)=2\log(n)+\dfrac{n}{2} $. Find $g(n)$ so that $f(n)=O(n)$. $ T(n)=T(n-2)+1$, $T(1)=T(0)=1 $ Find $g(n)$ so that $T(n)=O(n)$. It's supposed to be two simple questions but I guess that I didn’t ...
3
votes
1answer
33 views

Finding all local $k$-maximums in sequence $a_1, a_2, \ldots a_n$.

For given sequence of numbers $a_1, a_2, \ldots, a_n$ we say that $a_i$ is $k$-local maximum, if $i > k$ and $a_i$ is largest of numbers $a_{i - k}, a_{i-k+1}, \ldots, a_i$. How can we find all ...
0
votes
2answers
50 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
1
vote
1answer
75 views

Proof regarding notations

I tried to solve the following question: Let $f,g$ be non-negative functions such that $f(n)=g(n)\left[1+o(1)\right]$. Prove that $f(n)=\Theta(g(n))$. I looked on two cases: ...
0
votes
0answers
17 views

Matrix operation repeat matrix members

I am going to use C++ Armadillo library which handles matrices to generate matrix $B$ and $C$ from matrix $A$. $$ A=[M_0,M_1,\ldots,M_{n-1}]^T $$ $$ ...
2
votes
1answer
28 views

What's the meaning of “reuse space”?

I'm reading this. $\quad \;\;$ What's the meaning of reuse space in here?
1
vote
3answers
25 views

Prove of a Landau-equalities

I have to prove or disprove the following Landau-equalities: $$ O(f+g) = O(max(f,g))$$ and $$O(f-g) = O(min(f,g))$$ with $f,g: \mathbb N \to \mathbb R^+$ . To show equality of two sets, one has to ...
1
vote
1answer
59 views

Expected time of Quicksort

I am reading the proof of the theorem: The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time. The proof is this: For simplicity in the timing analysis assume ...
0
votes
1answer
16 views

Time complexity comparison between two functions

I'm confused as to how $f(n)$ can be $O(g(n))$, $\Theta (g(n))$ and $\Omega(g(n))$. Could someone help explain?
1
vote
1answer
25 views

Las Vegas Algorithms

In some notes i'm reading it says that the definition of a Las Vegas Algorithm is An algorithm which always outputs the correct answer but has unbounded running time, with the expected running time ...
1
vote
1answer
27 views

Computational complexity comparison between MINLP and MILP

Can someone please explain the computational complexity of MINLP and MILP, though both are NP-Hard. What is the advantage of having an MILP formulation over MINLP formulation for a same optimization ...
5
votes
1answer
53 views

Choosing primes uniformly at random

I'm interested in efficient methods of generating prime numbers in a given range [a, b] (or with a given number of bits/digits, etc.). By "efficient" I mean minimizing time, randomness, and perhaps ...
1
vote
3answers
34 views

What is the growth rate of the logarithm of the factorial sequence?

I'd like to know the space complexity of storing bit string representations of the numbers in the factorial sequence (as in a memoized factorial function). So each number $f_i=i!$ in $i=0 \cdots n$ ...
0
votes
0answers
21 views

Is there a universal constant for size of disjoint clauses in 3-CNF

We are given a 3-CNF formula $\Phi$ on n variables, and a guarantee that at least 1% of $2^n$ possible assignments satisfy all clauses in $\Phi$. Now construct set $S$ of disjoint clauses so that no ...
0
votes
2answers
39 views

Proof NP-Complete for $L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$

$L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$ and I try to prove it's NP-Completeness. It seems really easy since obviously it is at least as hard as HAM-PATH which is ...
1
vote
2answers
58 views

Are there undecidable problems for which a solution has been found?

I mean are there examples of problems that have been proven to be undecidable, in the sense that it would not be possible to devise a deterministic computer program that outputs a solution for an ...
0
votes
2answers
27 views

Can a function exist that is both $o(g(n))$ and $\omega(g(n))$?

Can a function exist which is both $o(g(n))$ and $\omega(g(n))$? Wouldn't this imply $$m |g(n)| \le |f(n)| \le k |g(n)| $$ If $f(n) = g(n)$ then wouldn't an arbitrary integer $m$ be greater ...