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)

3
votes
1answer
20 views

Are there slight modifications to NP-complete problems which reduce them to P?

Recently I revisited the infinite harmonic series and its barely diverging sum, and how removing all the composite numbers from the sum still produces a divergent series (even more barely). In ...
0
votes
1answer
9 views

The time complexity of the n-ary cartesian product over n sets

Recall that the Cartesian product $A\times A$ is defined as the set $\lbrace (x,y):x\in A ,y \in A \rbrace$ . Thus, if for example, $A=\lbrace 1,2,3 \rbrace$,$A \times ...
0
votes
0answers
28 views

Why aren't all NP-complete problems strongly NP-complete, if any NP problem can be reduced to an NP-complete problem

So we know that : (1). A problem is NP-complete if every other problem in NP can be reduced to it in polynomial time (2). A problem is said to be strongly NP-complete if a strongly NP-complete problem ...
0
votes
1answer
23 views

How many coins do we need to get $k$ amount

In the far away land of coinsville, they use $4$ different coins as currency, $\{1,10,100,200\}$ What is the computational class of the amount of coins (minimal!!) we need to get $k$ amount? Well, ...
0
votes
1answer
7 views

max degree polynomial for time complexity considerations

Is there some maximum degree for a polynomial for time complexity considerations and maybe P-NP considerations, maybe some high-degree polynomial formula identified by name, and associated with some ...
2
votes
1answer
18 views

Problem with my simple algorithm to count repetitions

We have two arrays $A,B$ with sizes $n,m$ respectively. We know that $m \geq n$. We also know that no array contains the same number twice. Propose an algorithm that prints how many numbers appear in ...
1
vote
0answers
20 views

How to properly detect rows to be swapped in a Gaussian elimination?

I'm trying to describe an algorithm for solving solvable linear systems. The Gaussian elimination is pretty straightforward in terms of adding multiples of rows. However, consider the following ...
0
votes
0answers
18 views

Computing the Log-Euclidean distance efficiently by using eigen-analysis.

Let $A,B\in\Bbb{S}_{++}^n$ be two symmetric positive definite $n\times n$ matrices with real entries. The Log-Euclidean distance between these matrices is defined as follows $$ d = \lVert \log(A) - ...
2
votes
3answers
34 views

Prove correctness of simple greedy algorithm to find max

We have $2n$ values $x_1,x_2,x_3,\ldots,x_n$ and $y_1,y_2,y_3,\ldots,y_n$ such that the pair $(x_i,y_i)$ represents the location of a city $i$. Assume there is no straight line that goes through all ...
1
vote
0answers
32 views

The definition about 'with high probability (w.h.p.)' [closed]

w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that: Assuming we ...
-1
votes
1answer
64 views

A quicker algorithm.

Consider an algorithm which essentially counts to a certain number then halts. Counting Algorithm C Given any $n \in \Bbb N$ Step 1 $x_0=0$ Step 2 $\text{if} (x_n =n)\ \text{then}(\text{halt}) $ ...
0
votes
1answer
67 views

Complexity of $\binom{n}{2}$

So: $$\binom{n}{2} = \frac{n!}{2!(n-2)!}$$ Using Stirling's approximation we have: $$\frac{\sqrt{2 \pi n}(\frac{n}{e})^n}{[\sqrt{2 \pi 2}(\frac{2}{e})^2][\sqrt{2 \pi ...
1
vote
2answers
76 views

Is there any sort algorithm quicker than Quicksort given a random array of integers?

How can we proof (mathematically) that any complexity of sorting algorithm that sorts a random array of integers is no better than $O(n\log n)$?
4
votes
1answer
102 views

What background is needed to study quantum game theory?

Currently I am learning ( a beginner ) about Bell inequalities and device independent outlook on quantum mechanics. I come across some papers using these concept in quantum game theory. Most of the ...
0
votes
1answer
47 views

Is finding generators of finite fields hard?

Task: Given $n$, find a generator of $GF(n)^*$. Is there any evidence this is hard? Maybe a reduction from another problem presumed hard? Finding the orders of elements should be hard because I ...
2
votes
3answers
30 views

A=LU decomposition time complexity

I am trying to derive the LU decomposition time complexity for an $n \times n$ matrix. Eliminating the first column will require $n$ additions and $n$ multiplications for $n-1$ rows. Therefore, the ...
0
votes
1answer
22 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
1
vote
0answers
20 views

Prove that $S_2$ is closed under union and complement

I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that: It is immediate from the definition that $S_2$ is closed under union ...
2
votes
1answer
39 views

Is there an algorithm to find minimum number of undefinable words in a dictionary?

Here's the problem. Every word in a dictionary is defined by a set of other words. For example "cat" may be defined as "small mammal with fur". Can we choose a set of 'base' or 'prime' words such that ...
-1
votes
0answers
18 views

given a language L proof via direct reduction ATM < L.

Regarding my previous question: Direct Reduction, Turing machine and a DFA here agaian: > L ={ < M , D >| M is s TM and D is a DFA so that L(M) = L(D)} ...
0
votes
1answer
10 views

Invent a polynomial algorithm to find max non-degenerate minor

There is a matrix $A$ with $n$ rows and $m$ columns. The task is to invent a polynomial algorithm to find non-degenerate minor of maximum size. If I got it right, we can reduce this to Gaussian ...
1
vote
0answers
21 views

Is there a polynomial time algorithm for Poly-trees (oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
1
vote
0answers
38 views

Is there a “C vs NC”-problem, where C stands for “constant time”?

Appologies if this question is utterly naive. I know very little about complexity classes, but like to learn more. Consider the following problem. Given input $n$ (a natural number) we want to find ...
0
votes
1answer
16 views

Set of edges is MST?

Given a Graph $G = (V,E)$ and given a subset $ T \subset E$. I would like to test, whether T is already a MST of G or not in constant time. Note: If $T^{MST}$ is the MST of G, then we know that $T ...
0
votes
0answers
6 views

Highly optimized systems

I'm interested in the idea that highly selected causal systems exhibit general behaviors and properties. By causal systems I mean formal systems that progress from a defined set of starting conditions ...
0
votes
0answers
18 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
41 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
22 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
56 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
222 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
49 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
23 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
73 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
30 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
41 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
67 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
31 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
43 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
32 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
39 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
52 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 ...