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)

2
votes
1answer
33 views

Doubt about claim about complexity of edge coloring powers of the line graph

Likely I am misunderstanding/missing something, but a claim in a paper appears wrong to me. According to Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation p. 2 Unless ...
2
votes
1answer
15 views

Is it known whether a hypothetical P-time NP-complete decision procedure has to find a specific solution to the given constraint satisfaction problem?

Suppose a hypothetical decision procedure $A$ could solve NP-complete problems in polynomial time (of course implying $NP = P$). Many NP-complete problems take the form of constraint satisfaction, ...
2
votes
1answer
16 views

Show that $\log^{i} n \in O(n^{j})$ for $i,j > 0 $

I want to show that $$\log^{i} n \in O(n^{j})$$ I tried to apply L'Hospital and came up with the following: $$\lim\limits_{n \rightarrow \infty}{\frac{\log^{i} n}{n^{j}}} =$$ $$\lim\limits_{n ...
2
votes
1answer
74 views

Why doesn't the decision problem for Presburger arithmetic demonstrate that $\mathsf{P} \neq \mathsf{NP}$

From Wikipedia's article on Presburger arithmetic: Then Fischer and Rabin (1974) proved that any decision algorithm for Presburger arithmetic has a worst-case runtime of at least $2^{2^{cn}}$, ...
0
votes
0answers
14 views

Time Complexity of algorithm

Suppose I have an output of roughly $n^k k \log_{10} n$ digits where $A$ has $n$ elements and we have to list $n^k$ tuples with $k$ components each. What would be the time complexity class of such a ...
0
votes
1answer
21 views

$O(\text{polylog}(1/\epsilon))$-time Algorithm for Numerical Integration to Within Additive $\epsilon$?

I'm trying to approximate a 1D definite integral to within an additive $\epsilon$ for a given $\epsilon$. I was wondering whether there is an $O(\text{polylog}(1/\epsilon))$-time algorithm for this. ...
3
votes
1answer
26 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
16 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
30 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
votes
1answer
66 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
103 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
48 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
32 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
21 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
19 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
22 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
42 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
58 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
51 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
24 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
68 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
32 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 ...