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

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
18 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
30 views

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

$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 [on hold]

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

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

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
25 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
22 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
15 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
32 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
21 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
30 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
73 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
57 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
24 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
52 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
32 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
57 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 ...
1
vote
0answers
34 views

Complexity of combination method

I have a question about complexity of combination two methods. Assume that I have method A with its complexity is $O(n)$ and second method that has complexity is $O(n^2)$. In which, n is number of ...
0
votes
2answers
88 views

Proof of a Landau-inequality

I have to prove or disprove the following: $$ 2xlog_{10}((x+2)^2) + (x+2)^2log_{10}(\frac x2) \in O(x^2log_{10}(x))$$ My approach (with $log$ is meant $log_{10}$): $4x log(x+2) + (x+2)^2log(x) - ...
0
votes
2answers
36 views

Find both the largest and second largest elements from a set

Consider finding both the largest and second largest elements from a set of $n$ elements by means of comparisons. Prove that $n+\lceil \log n \rceil -2$ comparisons are necessary and sufficient. ...
0
votes
1answer
19 views

complexity question regarding whether it is decision problem

When self teaching complexity theory and seeing arguments that were made online. I get some confusion. In the class, we classify problems into P: can be computed polynomially NP: given a claimed ...
0
votes
1answer
39 views

NP-completeness of Ising model

In this paper: http://www.brown.edu/Research/Istrail_Lab/papers/p87-istrail.pdf It is claimed that calculating partition function of 3 dimensional ising model is NP-complete. But I have a question, ...
0
votes
1answer
34 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?
1
vote
0answers
82 views

smallest circuit

Let $SMALLESTCIRCUIT$ be the language consisting of all Boolean Circuits $C$ with the property that there is no smaller circuit $C^{'}$ that has the same truth table as $C$. (smaller means having ...