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

Algorithm - Maximum subarrays with sum and OR

I was thinking on the following problem: Given an array A. The value of an interval from i to the index j is defined as follows: Take the maximum value from that interval, and add it to the OR ...
0
votes
1answer
60 views

What does $\{0, 1\}^*$ mean?

I am reading about Polynomial probabilistic time (PPT) and the input is taken from space $\{0, 1\}^*$ and I am not able to understand how is this working.
0
votes
1answer
24 views

Complexity of Newton iteration problem for a d-dimensional problem

If we assume that we have $f:\mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ and we want to use the Newton iteration method to solve $f(x)=0_{\mathbb{R}^{d} }$. Is there any theorem regarding the ...
1
vote
1answer
36 views

Combinations for pairing groups

I have a little bit of a complex question and I don't know anything about combinatorics, but I'm working on software problem and I'm trying to figure out how my algorithm will scale. I'm having to ask ...
3
votes
2answers
58 views

CLIQUE to UNARY-CLIQUE reduction NP complete

Assume the following Language: UNARY-CLIQUE= $\{(G=(V,E),1^k) \mid G$ is an undirected graph and there is a clique of size $k$ in $G\}$ I'm trying to determine whether this language belongs to NP ...
0
votes
1answer
26 views

What is the difference between finding the sum of a series and its closed-form solution?

In complexity theory, it is sometimes necessary to find the "closed-form solution" of a summation. This was put in our exam guide as "solving arithmetic and geometric series", which I initially ...
1
vote
1answer
32 views

What's the fastest known running time for a spigot algorithm for computing an arbitrary digit of $\pi$?

That is, for the fastest known algorithm for doing so, how many steps will it compute the $n^{\text{th}}$ digit of $\pi$ in? I know some people define running time as the number of steps it will take ...
2
votes
1answer
28 views

How to show that the Restricted-3-color decision problem is in the polynomial class

I'm struggling to answer a past paper question, which asks to prove that the defined problem is in the polynomial complexity class(P). The question is mentioned below The only strategy I can come ...
6
votes
2answers
37 views

If there isn't currently a working algorithm to solve a chess problem and win the game, how do user-vs-computer chess games work?

I was watching a video on Computational Complexity and the lecturer mentioned that "we do not current have a algorithm to allow us to win a game of chess". If so, I'm interested in knowing how chess ...
-3
votes
2answers
72 views

Can someone provide me a simplest way to calculate: [closed]

$42^{17} \pmod{3233}$ I know the answer is 2557 - But I need to know how to calculate this without help of a machine that generates the answer. Thank you!
3
votes
0answers
45 views

NP-complete impossible to solve in $O(n)$

NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small ...
3
votes
2answers
199 views

How to calculate a Modulo?

I really can't get my head around this "modulo" thing. Can someone show me a general step-by-step procedure on how I would be able to find out the 5 modulo 10, or 10 modulo 5. Also, what does this ...
-2
votes
0answers
23 views

How to reduce the Partition Problem to 3-Partition?

Given a set of natural numbers. Show the problem of following is NP-complete: decide if the set can be partitioned into three disjointed subsets that have equal sums and the union of them is the ...
0
votes
0answers
18 views

To prove a language is not recursive

Prove the language $$L_1=\{\sigma\in\{0,1\}^*|\sigma \text{ codes a TM which accepts at least one word }\}$$ is not recursive. I think it has something to do with $$L=\{\sigma\in\{0,1\}^*|\sigma ...
1
vote
2answers
46 views

Proof that **NP=P** implies **NP=NPC** [closed]

As the title says, I am not sure how the former implies the latter. Please someone sketch a few details. Many thanks
0
votes
1answer
14 views

Binary Search 2Log(n)+1 steps?

So this is probably a basic and slightly stupid question. So.....for a binary search to find a number it takes at most 2Log(n)+1 steps (or Log(2N) questions. Im not a math major or anything, but ...
0
votes
0answers
22 views

Cholesky of Matrix plus Identity

I have a positive definite matrix $A$ ($n \times n$ dimension) for which I have the Cholesky decomposition $A=LL^{'}$. I want to use this to compute a) The cholesky decomposition of $A+c^2\times I $ ...
1
vote
0answers
18 views

What do log-equivalent and log-complete mean?

I'm reading the paper The Complexity of Satisfiability Problems by Thomas Schaefer(1978). In the paper, he mentions the phrases "log-equivalent" and "log-complete." Searching through the Google ...
1
vote
0answers
10 views

Simplicial maps between simplicial 2-manifolds

Suppose I have two simplicial two-manifolds ("triangle meshes") $M_1$ and $M_2$. I want to compute a surjective simplicial map between $M_1$ and $M_2$, i.e. a surjective function $\phi$ between the ...
3
votes
3answers
64 views

Wouldn't each addition take time $O(n)$?

I am going over the asymptotic runtime of regular matrix multiplication. Here is a lecture slide I am referencing(too much to type out, shown below), from Algorithms Everything makes sense up ...
0
votes
0answers
22 views

Runtime Complexity | Recursive calculation using Master's Theorem

I have the following recurrence relation (arising from some kind of augmented merge sort): $$ T(n) = T\left({2n\over5}\right) + T\left({3n\over5}\right) + n$$ and I need to find the worst-case ...
2
votes
1answer
26 views

Proving a language $L$ is in $\mathrm{co\text{-}NP}$ if $| L \cap \{0,1\}^n | \in \operatorname{poly}(n)$ for all $n$

Let $L \in NP$ such that $|L \cap \{0,1\}^n|=\operatorname{poly}(n)$ for all $n$. Prove that $L \in \mathrm{co\text{-}NP}$. If I understand the problem correctly, in words this says that "for any ...
1
vote
0answers
36 views

Coppersmith-Winograd algorithm

I'm interested in algorithms to compute matrix multiplications. Is the Coppersmith-Winograd algorithm similar to the Strassen algorithm ? I have two other questions: 1) Are the multiplications done ...
0
votes
0answers
24 views

How to approximate a trigonometric to make less computation complexity

I having a trigonometric function such as $$ p_2(s) = \begin{cases} \frac {1}{(2 \pi)^2}(1-\cos (2 \pi s)), & \text{if $s \le1$ } \\ \frac {1}{2 }(s-1)^2, & \text{if $s >1$ } ...
1
vote
1answer
32 views

Approximation of combination $ {n \choose k} = \Theta \left( n^k \right) $?

Is it a valid to say $$ {n \choose k} = \Theta \left( n^k \right) $$ for any $n$ and $k$? If so, how to prove it? Note: $k$ is not a function of $n$. Note: Observed it here (page 5): ...
0
votes
1answer
26 views

Why is $O(n^{km}+n^m)=O(n^{km})$?

I've seen this equation in one of my handouts $O(n^{km}+n^m)=O(n^{km})$, which doesn't seem obvious to me. This is what I got trying to work it out: $$\begin{align*}n^{km}+n^m &\leq C \cdot ...
0
votes
0answers
16 views

Recommended gentle introductory reading for computational complexity

I recently read this paper by Scott Aaronson titled: 'Why Philosophers Should Care About Computational Complexity'. I came across it via a link in Hacker News As somebody with a general interest in ...
1
vote
2answers
41 views

Is showing a graph is non-Hamiltonian NP-Complete?

Show that graph is not Hamiltonian. Is this an NP-complete problem? My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle ...
0
votes
0answers
11 views

Arithmetic circuit and complexity

Why scalar multiplications and additions can be considered free when looking at arithmetic circuits ? Thank you.
3
votes
2answers
83 views

An easy question about NP-hard

Consider an optimization problem includes two variables. If we fix the value of one variable, then the optimization problem over the other variable is NP-hard. Can it be concluded that the original ...
1
vote
2answers
44 views

Quick solution check for the TSP

Given a solution for the Boolean satisfiability or the Hamilton cycle problem it's obvious whether it's true or not, but how does one quickly check whether a solution for the TSP (travelling salesman ...
0
votes
1answer
6 views

Given $L = L_1 \cap L_2$ where $L_1 \in NP$ and $L_2 \in coNP$, how do I express L as a symmetric difference of 2 sets in NP?

My ultimate goal is to show that $L \in PP$, but I need to figure out the title question first as an intermediary step. Any help is appreciated, thanks in advance.
3
votes
1answer
21 views

Computational Theory: Proof, Chomsky normal form

Prove or disprove: If $G$ is a CFG in Chomsky normal form, then for any string $w \in L(G)$ of length $n\geq 1$ then exactly $2n-1$ steps are required for any derivation of $w$. I'm stuck at where to ...
3
votes
0answers
49 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
0
votes
0answers
12 views

Depths of top-level multiplication algorithms

I've seen that the depth of the Cantor/Kaltofen algorithm is in $O(\log n)$. Are the operations for this complexity undifferentiated ? Or this complexity is in terms of multiplications only ?
0
votes
0answers
7 views

BFS Modification For Total Shortest Paths

I was given the following problem as an assignment but it is really confusing me: Consider the BFS algorithm. Given a digraph G = (V, E) and a starting vertex s ∈ V, this algorithm computes for ...
2
votes
2answers
68 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
0
votes
0answers
22 views

What are some techniques of specifying a molecules structure using the least amount of information?

For instance say I have a water molecule I can describe it's structure by two bond lengths and a bond angle. Are there any neat math tricks or representations of objects that I could use to describe ...
3
votes
1answer
56 views

Verifying whether a number is the determinant of a matrix

What is the (computationally) fastest way to determine whether a number is the determinant of a given real matrix? I am wondering if I have an upper bound on the absolute value of the determinant of ...
1
vote
0answers
19 views

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that $$c(\tau(a),\tau(1))+\sum_{i=1}^{a-1} c(\tau(i),\tau(i+1))\leq b $$ Prove ...
1
vote
0answers
41 views

Is there an optimal algorithm to calculate $2^n - 1$ in $\theta(n^n)$

The sequence $(f_{n})_{n \in \mathbb{N}}$ is defined by $f_{0} := 0, f_{1} := 1$ and $f_{n} := 3f_{n-1}-2f_{n-2}$ for $n \in \mathbb{N}_{0} \setminus \{0,1\}$. Is there an algorithm that takes an $n ...
2
votes
4answers
55 views

Two non-negative functions $\,f,g$, such that $\,f \not\in \mathcal O(g)$ and $ g \not\in \mathcal O(\,f)$

Show that there exist two non-negative functions $\,f,g: \mathbb{N} \rightarrow \mathbb{R}$ such that $\,f \not\in \mathcal O(g)$ and $ g \not\in \mathcal O(\,f)$. It would be easy two find two such ...
1
vote
1answer
38 views

Directly Obtaining the $n$th Value of a Lucas Sequence

(As an aside: This question lies relatively upon the border between the realms of Computer Science and Mathematics, and thus may be appropriate for StackOverflow as well.) I am in need of a method of ...
1
vote
0answers
54 views

the sum of the reciprocals of the primes

The sum of the reciprocals of the primes is $\sum \limits_{p}\frac{1}{p} \approx N \ln\ln(N)$ what about this sum where $p_{3}=3,p_{5}=5,p_{n}=\sum \limits^{N}_{j=5}\frac{1}{p_{j}} \sum ...
0
votes
0answers
13 views

Time complexity of a recursive function on a given set

I am computing a function $fun$ which is defined as follows. $fun(m,s)=\sum_{\sigma_{p}\subset s;|\sigma_p|=m}\left [\prod_{i}i\in \sigma_p \sum_{j=1}^{|s-\sigma_p|}\sum_{\gamma_p\subset ...
1
vote
1answer
27 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
1
vote
1answer
33 views

If $ f(n) = \sum_{i = 1}^{n} (n / i) \log(n / i) $ and $ g(n) = n ~ {\log^{2}}(n) $, then is $ O(f) = O(g) $?

I was trying to prove that if $$f(n) = \sum_{i=1}^{n}\frac{n}{i} \log\frac{n}{i} $$ $$g(n) = n \log^2n$$ then $O(f(n)) = O(g(n))$ I am not sure that it is the case, but based on my simulation ...
1
vote
0answers
55 views

Counting problem of combinations of symmetric matrix.

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below- $G$ is partitioned in to two sub ...
0
votes
2answers
49 views

P vs NP and Countable vs Uncountable Decision Space

I have noticed that whenever the scope of a problem is pushed to infinity, problems in NP have an uncountably infinite decision space whereas problems in P seem to have a countably infinite decision ...
0
votes
0answers
13 views

Find all groups that meets the condition

I have $n$ elements, each of them have two unsigned int attributes $x$ and $y$. Now I'd like to find out all the groups that fit the following condition: $A.x \geq B.y$ and $B.x \geq A.y$. The ...