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
1answer
38 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
60 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 ...
2
votes
0answers
43 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
28 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
37 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
16 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
74 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
39 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
88 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
21 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
47 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
42 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
72 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
39 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
33 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
24 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
30 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
34 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
47 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
35 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
38 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
51 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
77 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
20 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
30 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
72 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
31 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
36 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 ...
2
votes
1answer
60 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
68 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
43 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
2answers
80 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
68 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
29 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
64 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
93 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
48 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
21 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
52 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
78 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
97 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 ...
0
votes
2answers
37 views

3-COLOR Decision Problem

The 3-COLOR problem takes as input a graph and decides whether it can be colored using only 3 colors so that no 2 adjacent nodes have the same color. The reduction from 3-SAT to 3-COLOR uses the ...
2
votes
2answers
119 views

Efficiency of a max-min problem for $\sum_{j=1}^m |b_j-a_j|$ with $a_i$, $b_j$ restricted to convex sets

Consider the following optimization problem: $$\max_{\{a=(a_1,a_2,\ldots,a_m)\in A\}}\min_{\{b:=(b_1,\ldots,b_m)\in B\}} \sum_{j=1}^m |b_j-a_j|.$$ Is computing the optimal value of this problem ...
0
votes
0answers
16 views

QBF - space complexity in detail

As I'm new to the "complexity theory" stuff I've some trouble with proofs which are "obvious" regarding all books I've found so far. In this case I want some evidence why a certain algorithm has space ...
1
vote
1answer
148 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
1answer
33 views

Calculating $b_1,b_2,…,b_k$ where $b_i$=$a_1a_2…a_{i-1}a_{i+1}…a_k$ in minimal number of multiplications

Let's suppose we have a set of integers $a_1, a_2, ..., a_k$ in $Z_n^{*}$, and that we define $b_i$ to be the multiplication $a_1a_2...a_{i-1}a_{i+1}...a_k$. Is there a way to calculate the set ...
0
votes
1answer
41 views

How can we show that $\lim_{n \to +\infty} f(n)=+\infty$?

We suppose that $\lim_{n \to +\infty} f(n)=+\infty$. I want to prove that if $f(n)=O(g(n)), c \in \mathbb{R}$, then $f(n)+c=O(g(n))$ . $f(n)=O(g(n))$ That means that $\exists c_1>0, n_2 \in ...
-1
votes
2answers
51 views

How may occupied positions are there?

Consider an array, that can have a huge ( or infinite ) number of positions, but only the first $n$ positions are occupied(only $n$ of them contain valid elements), and the remaining are empty. ...