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

Cost of an algorithm or an operation

In my notes there is the following: $G$: finite abelian group If $|G|=m$ elements we need $\lfloor \log_2 m \rfloor+1$ digits to represent all the elemets of the group. For example, ...
0
votes
0answers
47 views

How to calculate $\log \log \log N$?

How to calculate $\log \log \log N$ effectively? Is this problem polynomial? I tried to solve this by my own, but I still have no results and ideas. I think there is a solution better than ...
1
vote
1answer
25 views

Computational complexity of the algorithm

Make an analysis of the computational complexity of the algorithm below, where it is given by the number of elementary operations that the algorithm performs (assignment is not considered). Where ...
0
votes
1answer
60 views

Complexity of Least Common Multiple

I would like to know the complexity of computing the least common multiple of $n$ natural numbers. Does it depend on Euler's totient function?
0
votes
1answer
223 views

Basic idea of proof

I am trying to understand the proof that the expected running time of quicksort is $O(n \log n)$. Could you maybe explain me the basic idea? I am confused right now. EDIT: Suppose that we use the ...
1
vote
1answer
19 views

How $x \mod 2$ is in Elementary?

The function $$x\mapsto x\mod 2$$ should be in the complexity class Elementary (click it to see the definition of wikipedia). But using the definition, I don't see how to combine the functions to ...
0
votes
1answer
54 views

reduction from 3sat to 3 dimensional matching.

I've been reading about the standard reduction from 3sat to 3DM and my question was regarding the 'clean up gadgets'. So suppose i take an instance of 3-Sat with $n$ variables and $k$ clauses. Once we ...
0
votes
0answers
27 views

What is the difference between “DTIME” and “Big O” notation?

I have some understanding of "big O" and "little O" notation. I have heard of "DTIME" but have not had formal education or training regarding its use. Can someone explain the difference (or ...
-1
votes
1answer
22 views

How to compute the time complexity for a recurrence relationship?

I have to compute the time complexity for this recurrence relationship: T(n) = \begin{cases} c1, & \mbox{if } n\mbox{ = 1} \\ 8T(n/4) +n +c2, & \mbox{if } n\mbox{ > 1} \end{cases} Can ...
0
votes
0answers
11 views

Prove that $ALL_{CFG}$ is undecidable by reducing from PCP

I'm studying for a Computability exam that I have in a few weeks, and have come across this question which I'm having a hard time solving: Prove that $ALL_{CFG}=\left\{ \left\langle ...
0
votes
1answer
19 views

Time complexity function

I'm not sure I should post this on the Mathematics website or the Computer science website of Stack Exchange. If I'm wrong I will replace my question. So I'm trying to calculate the time complexity ...
2
votes
1answer
32 views

Is $P^{SAT}$ equal to NP $\cup$ co-NP?

I have following problem: Is $P$ with a $SAT$ oracle equal to $NP \cup coNP$ assuming that $NP \neq co-NP \neq P $? I can show that $NP \subseteq P^{SAT}$ and $coNP \subseteq P^{SAT}$. But it is much ...
0
votes
1answer
24 views

Reduction from Circuit-Sat to 3-Sat

I'm reading the following notes on reduction from circuit-sat to 3-sat http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf On the third page i'm unsure how they arrived at the following In ...
2
votes
1answer
17 views

Subgraph isomorphism problem

Subgraph isomorphism problem is an NP-hard problem. However, if the subgraph size is constant (assume $k$), then it can be polynomial time solvable. The most easiest way is that: Randomly obtain $k$ ...
2
votes
1answer
74 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
65 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
55 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
42 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
1answer
72 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
34 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 ...
2
votes
1answer
44 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
39 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
46 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 ...
-2
votes
2answers
77 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
53 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
3answers
843 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 ...
0
votes
0answers
25 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
49 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
17 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
35 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
24 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
15 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
70 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
32 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
28 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
58 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
32 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
58 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
28 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
44 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
13 views

Arithmetic circuit and complexity

Why scalar multiplications and additions can be considered free when looking at arithmetic circuits ? Thank you.
3
votes
2answers
86 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
50 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
24 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
53 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
15 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
16 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
80 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 ...