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
0answers
256 views

Polynomial Time Root Extraction

Given a consistent system of polynomial equations: $A_1(x_1, x_2, x_3 ... x_n) = 0$ $A_2(x_1, x_2, x_3 ... x_n) = 0$ etc... $A_n(x_1, x_2, x_3 ... x_n) = 0$ If we let $d_1, d_2, d_3... d_n$ be the ...
2
votes
0answers
130 views

Finding a matching to connect subsets of vertices

I'm studying a graph problem which, strangely, has applications in bioinformatics. I'm not asking for a solution, but rather for advice as to whether something similar to what I do has been studied ...
0
votes
0answers
194 views

Mathematical reason for 2-player turn-based games

I've been reading Games, Puzzles, and Computation which analyzes games through game theory and complexity theory. The authors introduce something called "Constraint Logic" as a way of modeling games ...
2
votes
2answers
871 views

How to reduce 0-1 knapsack to knapsack-like problem with overflow?

Consider a knapsack-like problem where there is a set of items, and each item has a cost $c_i$ and value $v_i$. The goal is to find a subset $S$ that minimizes $\sum_{i\in S}c_{i}$ with the constraint ...
0
votes
1answer
47 views

Complexity of bounded 2-player game

I was reading about bounded 2-player games in chapter 6.1 of Games, Puzzles, and Computation. "Bounded" here means theres some finite resource of the game which imposes a limit on the number of player ...
0
votes
0answers
27 views

Vertex Set Optimization

I have the following problem: Min $c^Tx$ Subject to: $Ax = b$ $x >= 0 $ Where A is an M x N matrix: But rather a single solution I would like to know the first K best solutions where $1<= ...
0
votes
0answers
32 views

A computational complexity problem

Consider $n$ arbitrary (but fixed) unit-norm vectors $\mathbf{x}_1,\ldots,\mathbf{x}_n$ in, say, $\mathbb{R}^d$. Let $\beta>0$ be fixed. For $\mathbf{y}\in\mathbb{R}^d$, define the binary ...
0
votes
1answer
43 views

Converting Maximum TSP to Normal TSP

Consider the Travelling Salesman Problem: Given N cities connected by edges of varying weights. Given a city A what is the shortest path for visiting all the cities exactly once that returns back to ...
6
votes
3answers
279 views

Which is easier to work out: determinant or inverse?

Suppose $A\in M_n(R)$ be a $n\times n$ matrix over some ring $R$. Which of the following two tasks is easier? to work out $\det(A)$; to work out $A^{-1}$. More specifically, I want to know the ...
1
vote
1answer
663 views

Absolute value optimization

If you have an LP Maximize/Minimize: $c_1|x_1| + c_2|x_2| ... c_n|x_n|$ Subject to: $Ax = b$ Can this be solved in polynomial time with respect to the amount of data used to represent the ...
2
votes
1answer
161 views

How much slower is a Turing Machine if you only give it one end of the tape to work with?

Turing Machines start with the input string and tape head in the "middle" of a tape that extends infinitely in either direction. Suppose instead that the tape head starts at the "far left" of the ...
0
votes
2answers
92 views

How to work out the inverse matrix $A^{-1}$ ?

Suppose A is a matrix over some ring R (might be non-commutative). How to work out the inverse matrix $A^{-1}$?
8
votes
1answer
501 views

efficient summation of $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$

I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} A_{ij}A_{jk}A_{ki}$, where $A_{ij}$ is the a ...
2
votes
0answers
120 views

Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
1
vote
1answer
158 views

$\Sigma_k^\text{P}$−SAT definition is not clear to me

I don't understand if by saying there are $k$ alternating quantifiers on the variables $x_1$,$x_2$...$x_k$, It means we quantify ALL variables (there are only $k$ variables in the SAT formula) or just ...
1
vote
1answer
92 views

What sequences / algorithms does $O(N \log\log N)$ limit?

Considering the big-o-notation, there are a variety of algorithms that have the $O(N \log N)$ computational complexity; such algorithms are for example the merge sort, fast fourier transform, etc. ...
2
votes
0answers
131 views

Comparing two character tables

Suppose that you are given two finite groups, for example, via their Cayley tables. One can efficiently compute their character tables (efficiently = polynomial time in the order of the group), this ...
1
vote
1answer
37 views

Finding the complementary language of a given language

I'm trying to figure out what's the complementary language of: L = {w#w : w∈{a,b}*, |w| = k} I think it's the language of all the words w#w where |w|!=k. I think my answer is not correct. How ...
2
votes
1answer
132 views

What does noncomputable really mean?

I believe I understand the definition of a noncomputable problem from an introductory computer science class, but I don't understand what it really means. One of my hypothesis was that a ...
9
votes
1answer
134 views

Homomorphism for a fixed graph NP-complete?

Let $G$ be the following Graph: We want to decide whether for an input structure $\mathcal{S}$ there exists a homomorphism $S \to G$. We will call this problem $HOM_G$. The task at hand is to show ...
0
votes
0answers
179 views

Its just one point… How do I find it?

Okay so here is the deal... I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$) and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$ where $0 \le ...
2
votes
1answer
677 views

Pseudo inverse of matrix: SVD vs $A^{T}(A.A^{T})^{-1}$

For a C++ implementation I have to calculate Moore Penrose Inverse (AKA pseudo inverse) of non squared matrices. I was wondering ...
3
votes
2answers
111 views

COMPOSITE $\in$P if and only if PRIME $\in$ P

Let COMPOSITE be the following decision problem. COMPOSITE Input: an integer $n \geq 2$. Question: is n composite? Show that COMPOSITE $\in$P if and only if PRIME $\in$ P. I think ...
0
votes
1answer
174 views

Finding average-case time complexity

I have an integer array and some x integer number. I'm looping through this array and compare each element with x, if there exists the exact element, the algorithm ends. The best case is B(n) = 1, ...
0
votes
1answer
86 views

algorithm to determine complexity of algorithms?

Given a decision problem X, can there exist an algorithm A which, given any algorithm B which solves X in finitely many steps, determines whether B runs in polynomial time? If such an A exists, when ...
1
vote
1answer
487 views

Integer Linear Programming (ILP): NP-hard vs. NP-complete?

I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind. It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
1
vote
0answers
30 views

How did we arrive at this form of Markov's Inequality in this proof?

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a proposition on $\textbf{ZPP}$($ \textbf{ZPP} = \textbf{RP} \cap \textbf{coRP}$-proposition $4.13$), ...
2
votes
2answers
54 views

Problem understanding a proof

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there's this example: Choosing an integer $a \in_R \{0,\dots,n\}$ using random bits. We assume that we ...
0
votes
1answer
43 views

Clarification on some mathematics formula

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a theorem on $\textbf{BPP}$ where I don't understand a few steps of its proof, it's totally independent ...
1
vote
1answer
51 views

Some problems about the proof of a theorem

There's a theorem in my book (Complexity and cryptography by Talbot and Welsh, chapter 4) where I don't understand some parts of its proof: THEOREM: Suppose $f \in \mathbb Z[x_1,..., x_n]$ has ...
2
votes
1answer
112 views

“Certificate” in the context of computational complexity

I can't find any definition for the word either in the book I am reading or online. What exactly does certificate mean in the context of computational complexity? For instance: [...]The above ...
1
vote
1answer
72 views

Input size measurement according to polynomial presenation

There's a paragraph in my book (Complexity and cryptography by Talbot and Welsh, chapter 4) that I don't fully understand: Let $\mathbb Z[x_1,\dots,x_n]$ denote the set of polynomials in n ...
8
votes
1answer
261 views

Applications of computation on very large groups

I have been studying computational group theory and I am reading and trying to implement these algorithms. But what that is actually bothering me is, what is the practical advantage of computing all ...
0
votes
1answer
46 views

Complexity of Code Snippet Without Knowing A Function?

I have the code snippet: int const n = 300; int nArr[n]; for(int i = 0; i<n; i++) { if(i >x) copyPrevious(nArr,i); } I need to find the complexity ...
1
vote
0answers
248 views

Calculate the time complexity for the following Travelling Salesman problem algorithm

Consider the following algorithm for solving the TSP: $n$ = number of cities $m$ = $n\times n$ matrix of distances between cities min = (infinity) ...
1
vote
2answers
168 views

Binary search complexity

In sorted array of numbers binary search gives us comlexity of O(logN). How will the complexity change if we split array into 3 parts instead of 2 during search?
0
votes
4answers
5k views

Big-O: Prove $2^n$ is $O(n!)$ [duplicate]

I am a little stuck trying to prove that $2^n$ is $O(n!)$. Obviously, I can tell in a few ways that this is the case. For one, based on Big-$O$ hierarchy, the exponential is beneath the factorial in ...
1
vote
1answer
348 views

calculating the determinant of an $n \times n$ integer matrix

I want to write a polynomial algorithm for calculating the determinant of an $n \times n$ integer matrix. There are various codes in different programming languages on the web but unfortunately I am ...
1
vote
1answer
79 views

What is the complexity class for each one of the following functions

What is the complexity class for each one of the following functions: $a) (n^3+n^2 \log n)(\log n+1) + (10 \log n+7)(n^3+3)$ $b) (2n + n^2)(4n^3 + 4n)$ $c) (n^n + n2^n + 3n)(n! + 6n)$
3
votes
1answer
233 views

Books on computational complexity

Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area? I've heard a thing or ...
1
vote
1answer
490 views

2-colorable belongs to $\mathsf P$

To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this ...
0
votes
2answers
42 views

Hardness of a special case of maximum matching

Input: A set of N Users $\{u_1, ..., u_N\}$. A set of M products $\{i_1, ..., i_M\}$. Every pair $(u,i)$ is associated with the probability of u purchasing the product i, $p_{u,i}$. Task: Assign ...
1
vote
0answers
2k views

How to calculate an orthonormal basis for a matrix?

Are there any specific, easy to compute, algorithms to build an orthonormal basis for a matrix in which each column has length one?
1
vote
1answer
379 views

Algorithm for topological sorting without explicit edge list

Suppose I have a set of vertices $V$ and a function $f(V_1, V_2)$ which given two vertices returns +1 if there is an edge from $V_1$ to $V_2$, -1 if there is an edge from $V_2$ to $V_1$, and 0 ...
2
votes
1answer
219 views

Simulating an alternating Turing Machine

I'm trying to figure out this question: Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice ...
1
vote
0answers
34 views

Computational Complexity of the class of $\Delta_0$ functions (over $V_\omega$)

I would like to know where the class of functions whose graph is $\Delta_0$ (over $V_\omega$) fits in the computational complexity hierarchy. Also is there a nice notion of $\Delta_0$-reducibility ...
0
votes
1answer
50 views

Proving an equality

Let $f(n) = n^ {\log n}$. Let $p(n)$ and $q(n) \geq n$ be polynomials. I want to show that for $n$ sufficiently large $f (n)$ satisfies $$p(n) < f (n) < 2^{q(n)}$$ starting from the above ...
1
vote
1answer
23 views

Notation about a randomized max cut algorithm.

http://users.cms.caltech.edu/~mccoy/publications/teatalk1.pdf I'm trying to understand the lemma in this. So we have Lemma Let $r$ be a random vector. For any unit vectors $u_{i}$ and $u_{j}$, ...
2
votes
1answer
82 views

Homomorphical Equivalence is NP-complete

Two graphs $G,H$ are homomorphically equivalent if there are exists a homomorphism from $G$ to $H$ and a homomorphism from $H$ to $G$. The task is to prove that this decision problem ...