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
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
60 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
28 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
40 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
1answer
13 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
21 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
23 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 ...
1
vote
1answer
47 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
60 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
41 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
17 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
112 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
168 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
21 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
910 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 ...
0
votes
0answers
29 views

Size of input relate to numbers of operations. Is it exponential?

Let assume that size of input is: $$ O( \log b + \log n) $$ and amount of operations on input is: $$O(b\log^2n)$$ Is amount of operations exponential relate to size of input? My intuition is: yes ...
0
votes
1answer
31 views

time complexity [closed]

Given n integers a1,a2..an and some integer S. To test whether there exists xi belongs to {0,1} such that: ...
1
vote
5answers
62 views

What's “computer's method” in calculating beta for a regression line

Since this is not from a problem set but just something I've been thinking, please forgive me for possible (wording) errors. Consider a set of data points $(x_n,b_n)$. We would like to know the ...
0
votes
1answer
33 views

Hardest boolean formula circuit complexity upper bound

I have stumbled upon Shannon's result that states that the maximum number of gates in a circuit needed to compute a boolean function on n bits, $f:\{0,1\}^n \to \{0,1\}$, is $\Theta (2^n/n)$. So far ...
0
votes
0answers
39 views

Proof of NP-completeness in the strong sense

I am just learning about the $\textbf{NP}$-completeness in the strong sense. I know that the $3$-partition problem: A set $X$ of $3n$ positive integers and a positive integer $B$ is given where each ...
0
votes
2answers
31 views

Is the concatenation of two arbitrary alphabets is considered an alphabet?

Is the concatenation of two arbitrary alphabets is considered an alphabet ? Also Is the set of all Java reserved words is considered an alphabet ? I am inclined to say yes. We could take a string and ...
0
votes
1answer
79 views

Is $P=NP$ an $NP$-complete problem?

Is $P=NP$ an $NP$-complete problem? In other words, is it possible (and does it make any sense) to show that proving $P=NP$ (or $P\neq NP$) cannot be done in polynomial time? I am not even sure it ...
0
votes
0answers
21 views

Turing machine that accept L = {ww} in linearithmic time

I was wondering if there is a way to design a deterministic turing machine that accept the language L = {ww} with a time complexity of O(n log(n))
2
votes
1answer
38 views

How many times will the statement 5 be executed?

I tried to calculate that, and I found that it is $\log n (\log n +1)(2\log n+1)$ ...
0
votes
0answers
29 views

Finding biconnected components of bounded size

Let $G$ be a simple graph with $n$ vertices where every biconnected component of $G$ has at most $c$ vertices. Let $v_1$ and $v_2$ be two adjacent vertices in $G$; $v_1$ and $v_2$ identify a unique ...
0
votes
0answers
13 views

Asymptotic analysis of an algorithm, difference between theoretical model and actual implementation.

I was wandering how a computational analysis should be performed in the following situations: Theoretical model Software model Let me show you an example (formula 1) $$x^2 = \sum_{i=0}^{n - 1} ...
1
vote
1answer
52 views

Derive a ϴ(1) formula for a Recurrence relation

I'm given a piece wise function with sequence $a_0$ $a_1$ etc $$a_n = \begin{cases}8 & n=0\\-7 & n=1\\25 & n=2\\7a_{(n-2)}+6a_{n-3} & otherwise\end{cases}$$ I'm asked to derive a ...
0
votes
1answer
22 views

Calculate bigO notation of recursive relation

I am attempting to calculate the big O notation for a simple recurrence relation $$T(n) = T(n/2) + 1\quad\text{when}\enspace n ≥ 1$$ $$T(1) = 1$$ So my attempt was as follows $$T(n) \le ...
2
votes
1answer
204 views

Giving an asymptotically tight bound on sum $\sum_{k=1}^n (\log_2 k)^2$

I am trying to give an asymptotically tight bound for the sum $\displaystyle\sum_{k=1}^{n} (\text{lg}k)^{2}$, where lg denotes the base 2 logarithm. I really have no idea where to begin, and I've ...
20
votes
3answers
749 views

Complexity of computing $ABx$ depends on the order of multiplication

To calculate $y = ABx$ where $A$ and $B$ are two $N\times N$ matrices and $x$ is an vector in $N$-dimensional space. there are two methods. One is to first calculate $z=Bx$, and then $y = Az$. This ...
1
vote
1answer
99 views

Big O with multiple variables ($n,m$): Is $O((n+1)^m) = O(n^m)$?

In the big O notation with multiple variables ($n,m$), is $O((n+1)^m) = O(n^m)$? Details: My intuition said yes, since adding a constant should neither have an effect in big O notation, even in a ...
0
votes
1answer
23 views

Is this proof of the worst-case performance of linear search correct?

I am sorry for the triviality of this question, but is this proof of the worst-case complexity of linear search correct? Claim. Let $L$ be a list of length $n$ and $k$ a target value in $L$. Then in ...
0
votes
0answers
19 views

What's a good book that touches on computational complexity theory and combinatorics?

I'm taking a class in enumerative combinatorics. The professor focusses on the complexity of solving combinatorics problems like partitions etc. I'm using Enumerative Combinatorics but it does not ...
0
votes
1answer
36 views

P is properly contained in DTIME(T'(n)).

There is a function T (which is not time-constructible, but is computable), such that $ P = DTIME(T(n)) \, . $ For every polynomial $p(n)$ , it holds that $p(n)=o(T(n))$. For every ...
0
votes
1answer
84 views

Worst Case Analysis

For the following algorithm, the function base() is to be considered the basic operation. The size of the input is given by n. Perform a worst-case analysis: for(i = 0; i < n; i++) for(j = 0; ...