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)

1
vote
0answers
27 views

tight bound for a finite sum involving harmonic series

I want to a know tight bound of this quantity when $n$ is even $$\sum_{k=1}^{n/2}\sum_{m=n-k}^{n}\frac{1}{k(k+1)m}$$. I simplified the expression and it comes like ...
0
votes
0answers
39 views

How could I modify a Turing machine that attempts to move the head past the leftmost square(crash) on some inputs so that it doesn't crash at all?

Suppose that M is a TM that crashes on some inputs. How would I modify M so that the new machine accepts the same language but does not crash on any input ?
0
votes
0answers
8 views

What is the time complexity of parallel approach of stable marriage?

There are many approaches to implement the stable marriage algorithm in parallel, I'm referring to the approach where the algorithm is divided into two phases. In the first phase the all the men are ...
0
votes
0answers
27 views

Does 3-SAT reduce to 3-CNF-SAT?

I know that SAT goes to 3-SAT and SAT is reducible to CNF-SAT and CNF-SAT is reducible to 3-CNF-SAT but is 3-SAT reducible to 3-CNF-SAT? They are not the same thing though right because cnf makes it ...
7
votes
4answers
251 views

How many possible phone words exist for a phone number of length N when also counting words less than length N within that phone number?

The phone words problem find all possible words that can be derived from a phone keypad, "words" do not have to be English dictionary words, for this question, words can be any combination of letters ...
1
vote
1answer
36 views

Algorithmic efficiency of rotating a point

I am trying to calculate the algorithmic effciency (Big-O) of rotating n 3-D vertices using the rotation matrix: $\begin{bmatrix}1 & 0 & 0 \\0 & cos(a) & -sin(a) \\ 0 & sin(a) ...
1
vote
1answer
33 views

How do we decide a problem is in NP, but not in P or NPC?

As I understand, NPC set contains only the problems which can be polynomially converted into each other and which are hardest in NP set/ But how do we decide which problems are in NPC and which ...
0
votes
0answers
44 views

nocomputable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
4
votes
1answer
177 views

Giving tight asymptotic bounds for $T(n)=T(\frac{n}{\log n}) + \log\log n$

I don't like coming here for such matters, but this is a homework problem from my Analysis of algorithms class. I've come along the Akra-Bazzi method and different variations on the matter , read ...
0
votes
1answer
51 views

not any computable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
5
votes
1answer
64 views

Is there a number $n$, such that there are $22$ groups of order $n$?

Denot : $N(n)$ : the number of groupfs of order $n$ ? Is there a number $n$ with $N(n)=22$ ? Checking the first about $2000$ numbers, I noticed that there is no $n\in [1,2000]$ with $N(n)=22$. ...
0
votes
0answers
17 views

How to devise an efficient algorithm to detect if every cycle of a weighted graph has, at least, two edges with the maximum weight

Let M be an adjacency matrix representing a weighted graph G. I'm trying to devise an algorithm to verify if, for every cicle C of G, the edge with biggest weight of C is not unique on C. I can think ...
3
votes
0answers
38 views

Is the problem : Determine the number of groups with order $n$ NP-hard?

It can be hard to determine the number of groups with order $n$, especially for $n=2^k$. So, I wonder, whether there is a polynomial algorithm doing this. I think, this is not the case because for ...
0
votes
1answer
20 views

How to start dealing with this recurrence relation

I have never seen a recurrence in this form, so I don't know how to proceed. I'm supposed to find asymptotic bounds (preferably $\Theta$(something)) for: $$T(n) =T\bigg(\frac{n}{\log n}\bigg)+ \log ...
1
vote
1answer
56 views

Time Complexity of Sorting Algorithm

Here's my question: Analyze the runtime of the following algorithm. Will it successfully sort array S of n elements with values from 0 to m-1? ...
1
vote
1answer
82 views

set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random ...
0
votes
0answers
18 views

Computational Complexity of exponentiating

I'm currently studying this paper and I am trying to understand the complexity of the interpolate algorithm, which is supposed to be $O((l+m)^2)$. So first the algorithm runs in $r$ steps where ...
0
votes
1answer
24 views

The approximability of different NP-hard problems

I'm fairly new to the topic Computational Complexity and had the following question (I therefore apologies before hand for any poorly stated terminology). Suppose i have two optimization problems ...
0
votes
1answer
23 views

Asymptotic complexity of power of logs

I'm trying to simplify $\Theta(lg^k(n/2))$. I believe it's $\Theta(lg^kn)$ but i don't know if the following proof is correct... i'd love to receive some input I tried doing - ...
0
votes
0answers
13 views

Np-hardness of a problem related to the knapsack problem

I am trying to know whether the following problem is NP-hard: Input: A positive number k and N pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
3
votes
1answer
44 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? ...
0
votes
0answers
18 views

$NP^A \neq coNP^A$(Baker, Gill and Solovay theorem)

From Baker, Gill and Solovay theorem we know that there is an oracle $A$ such that $NP^A \neq coNP^A$ Now what can we conclude from this if $A \in P$ or $A \in NP$ ? And correct me if I'm wrong, if ...
0
votes
1answer
52 views

What does $\forall X: A^X \subseteq B^X$ mean?

In Greg Kuperberg's complexity zoology inclusion diagram, there is a color coding based on whether or not $$ \forall X : A^X \subseteq B^X $$ is proven, disproven, or unknown. What does this ...
1
vote
0answers
15 views

A Complexity Problem of Cliques

I've been trying to figure out the Karp Reduction $$CLIQUE(G,k) \preceq IND(G,k),$$ Where $CLIQUE(G,k)$ is the decision problem "Is there a clique of size at least $k$ in the graph $G$" and ...
0
votes
1answer
27 views

Does storage scheme matter in multiplication of two matrices? [closed]

Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity ...
1
vote
1answer
31 views

Zero-One Optimization

I have looked through some resources with varying success. Perhaps someone can provide a place to start. Suppose we have a finite set of real numbers, $A$, and a partition, ...
0
votes
1answer
35 views

Complete trail - walk traversing each vertex at least once, each edge at most once

I would like to know the status of the following problem: Given a simple graph, is there a walk traversing each vertex at least once and each edge at most once? (I am asking for a complete trail, a ...
1
vote
1answer
29 views

Changing variable in summation

I'm trying to understand the analysis of Quick Select algorithm that I found on StackOverflow: http://stackoverflow.com/a/25796762/3356218 Case 1 of proof: I understand it but the first transition, ...
1
vote
1answer
13 views

Binary enconding length

What does binary-encoding length means? For instance if my theorem says "An algorithm solves in time which is polynomial in n and in the binary-encoding length $<l,u,b,w>$ of the rest of the ...
2
votes
0answers
10 views

Complexity notation (Omega) consequence

In my algorithms class, the professor told us that the following holds: $$ \text{If } f(n) = \Omega(\log_2 n) \implies 2^{f(n)} = \Omega(n)$$ But is this always true ? I couldn't come up with a ...
0
votes
1answer
28 views

What the proof, instance, and verifier mean in the definition of NP problem?

I came across a definition of NP problems: Definition. A decision problem $X ∈ NP$, if there exists a polynomial time verifier $V$ such that For every yes instance $x ∈ X$, there exists a ...
1
vote
0answers
38 views

Understanding AI through a complexity function

I've been trying to understand in light of a few apparent paradoxes for me. It appears reasonable that we could prove any mathematical problem that has a well defined answer can be solved by a ...
0
votes
0answers
18 views

Does 'polynomial' (or 'exponential') running time for 3-SAT problem refer to the number of variables or the number of clauses?

This sounds like an incredibly stupid question but none of the relevant Wikipedia pages seem to answer it. So... if the runtime of an algorithm to solve 3SAT has running time $O(f(n))$ for some ...
1
vote
0answers
22 views

Akra-Bazzi method - constructive proof

As I was familiarizing myself with different methods of computing complexities of recurrences, I stumbled upon the Akra-Bazzi method. Seeing such a beautiful result literally made my day. I was able ...
0
votes
1answer
46 views

equivalence of theory of reals and Rationals

Present a sentence φ that is in theory of reals but not in thoery of Rationals Following up from this question what is the approach to show that both the theories are equivalent Th(R, 0, 1, +, ≤) ...
-2
votes
1answer
58 views

P vs NP, finding algorithms in polynomial time?

Concerning an NP problem, such as the travelling salesmen problem. Say for a graph with N nodes there exists an algorithm $A(N)$ which can solve the problem in time $N^3$ (for example). But.... to ...
0
votes
1answer
46 views

Statistical distance and test

Here is a bit of context and definitions: Let $\mathcal D$ and $\mathcal E$ be distributions of probability over a finite set $A$ and $X, Y$ be random variables following $\mathcal D$ and ...
1
vote
1answer
37 views

How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $

I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ Can any body explain this to me in simple terms. Any help on this is highly appreciated.
1
vote
1answer
16 views

Convex hull from cloud of co-ordinates

I'm trying to design an algorithm to find the convex hull of a set of co-ordinates using the slope between two points to determine if a point is part of the convex hull. I'm testing a set of five ...
0
votes
0answers
20 views

Pspace Complete Problem

image1 image2 In theory of computation text book I was going through this problem ... I have added the images What I wanted to know is that in the middle of the problem it is given that "Using this ...
0
votes
1answer
26 views

Big O - Recurrence

I am given a function as follows: ...
0
votes
0answers
29 views

Complexity theory : Lower Bound for the Theory of Real Addition

In theory of computation text book I came across this page ... I have added the images I wanted to know what at the bottom of the page it is given that However,we can combine these into one ...
0
votes
0answers
111 views

Cover of vertices - NP Algorithm analysis, correctness and execution time

Introduction Given a graph $G = (V, E)$, we call a set $T \subseteq V$ a cover if any edge $e \in E$ has one extremity in T. Decision Problem: Given $G = (V, E)$ with n nodes and a $k \le n$, return ...
0
votes
0answers
9 views

lower bound Tutte polynomial for planar graphs

The Tutte Polynomial $T(G, x, y)$ s a #P-Hard problem except for the hyperbola (x-1)(y-1)=1 and some other specific points. For the case of planar graphs, Dell $\textit{et. al.}$ mention (in the ...
0
votes
1answer
140 views

How we decide for a given context free grammar generate an infinite number of strings?

Consider the following decision problems: (P1) Does a given finite state machine accept a given string? (P2) Does a given context free grammar generate an infinite number of strings? Which of the ...
0
votes
1answer
20 views

Getting big Oh from summation

Merging two sorted arrays $A_1$ and $A_2$ with $n_1$ and $n_2$ elements, respectively, takes $O(n_1+n_2)$ time. This strategy begins by merging two arrays of size $n$ to create an array of size ...
0
votes
1answer
22 views

Need help in understanding proof “approach” and meaning for “1st order Theory of dense linear orders w/o endpoints is PSPACE complete”

So in my class we are giving a proof for 1st order Theory of dense linear orders w/o endpoints is PSPACE complete. The proof that it is in PSPACE is basically to reduce TQBF. Let $\phi = \exists ...
1
vote
0answers
11 views

Comparing the orders of complexity.

I do have to evaluate a property defined as $$w = \sqrt{\det\left(\textbf{J}\,\textbf{J}^\text{T}\right)} = \prod_{i = 1}^n \sigma_i,$$ where $\textbf{J} \in R^{3 x n}$ and $n>3$. Using the ...
0
votes
0answers
40 views

Hilbert 10th, bounded arithmetic, NP=co-NP

I keep seeing claims that if Hilbert 10th, if can be proved in bounded arithmetic (specifically $T_{2}$), then it will automatically mean that NP=co-NP. Unfortunately, none of these claims provide any ...
1
vote
4answers
666 views

Newton form vs. Lagrange form for interpolating polynomials

I'm just wondering, what are the advantages of using either the Newton form of polynomial interpolation or the Lagrange form over the other? It seems to me, that the computational cost of the two are ...