Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

0
votes
0answers
23 views

About tensor methods in ML

I am referring to this paradigm as explained here, http://newport.eecs.uci.edu/anandkumar/tensor.html My question is this, do these tensor methods somehow promise to make non-convex optimization ...
3
votes
1answer
14 views

MIS complexity in cubic triangle-free graphs

The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the ...
3
votes
1answer
23 views

About the Max-Cut SDP

The Max-Cut optimization problem on a graph $G=(V,E)$ can be written as the question of wanting to maximize the function $\frac{1}{4} \sum_{(i,j) \in E } (x_i -x_j)^2$ under the constraint $x_i^2 = 1, ...
3
votes
1answer
27 views

How is the space hierarchy theorem different for non space constructible functions?

Sipser first introduces space constructible functions. Then uses the definition to prove the space hierarchy theorem: if f(n) is a space constructible function then there are languages that can ...
3
votes
1answer
48 views

Is matrix “adjoint-squaring” faster than general matrix multiplication?

The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are ...
1
vote
1answer
34 views

complexity of modal logic axioms

I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper. At the moment I have the following: K- no restrictions ...
4
votes
0answers
46 views

NL and NP compute different binary relations, so what?

Let the binary relation computed by a nondeterministic transducer be the relation between input strings and the possible output strings the transducer can produce (and accept) for the given input ...
2
votes
1answer
91 views

Polynomial hierarchy: inclusion between spaces

Using the definition for the polynomial hierarchy: $$ \Sigma_{i+1}^P = NP^{\Sigma_i^P} $$ $$ \Pi_{i+1}^P = coNP^{\Sigma_i^P} $$ I have been asked to to show that: $$ P^{\Pi_k^P } \subseteq ...
1
vote
1answer
37 views

How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? [duplicate]

I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem. Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the ...
5
votes
3answers
201 views

Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), ...
6
votes
1answer
167 views

Why is FACTOR in Co-NP?

I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS ...
-1
votes
0answers
16 views

What is wrong with the below complexity analysis of Universal Turing Machine's simulation? [on hold]

In Arora Barak at page no. 32 it says that once we perform the shift with $i$ index, the next $2^i - 1$ shifts of that particular tape will have all index less tha $i$. Since in total there can be $T$ ...
1
vote
2answers
83 views

Proving that the language of satifiable CNF formulae with primes is NP-complete

Given the following language: $$L=\left\{\langle\phi, n\rangle \ \middle|\ \begin{array}{l}\phi\text{ is a satisfiable Boolean formula}\\ \text{written as POS (in CNF form)}\\ \text{and $n$ ...
1
vote
1answer
32 views

About showing algorithmic gap instance for the Goemans-Williamson SDP

Using usual notation we have, $SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$ where we mean, $SDP(G)$ = The maximum value that the SDP finds of the objective ...
1
vote
1answer
28 views

L closed under logspace reduction

Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$. I read the proof that $L$ is closed under logspace ...
3
votes
1answer
515 views

Complexity of multiplication

I've been reading around the area of complexity and arithmetic operations using logic gates; one thing that is confusing me is that \begin{equation} \Theta (n^{2}) \end{equation} is quoted as being ...
4
votes
0answers
76 views

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
15
votes
4answers
3k views

Would proving P≠NP be harder than proving P=NP?

Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP. Let Q be one of known NP-hard problems. To prove P=NP, we need to design a single polynomial time algorithm A for Q and prove ...
-1
votes
1answer
32 views

Is the complement of the given language necessarily in NP?

$A$ is a given language so that $A \in NP$. Assume that $P = NP$. Is $A'$ necessarily in NP? What I did: $A \in NP , P=NP$ $P=coP$ (Can be proven by running a TM $M$ as a decider for ...
4
votes
0answers
85 views

How does the hardness of Subset Sum instances depend on their density? [closed]

The density of a Subset Sum instance $S = \{ s_1, \dots, s_n \}$ of size $n$ is defined as $\qquad\displaystyle d(S) = \frac{|S|}{\log_2(\max_{s \in S} |s|)}$. Why is the hardness of Subset-Sum ...
4
votes
0answers
39 views

What's the complexity of solving a packing LP?

As we know, we can solve general linear programs in weakly polynomial time and it remains open if it is possible to solve them in strongly polynomial time as well. But what is the situation in the ...
3
votes
0answers
46 views

Upper bound complexity for a tree's particular property

I want to determine if in a given binary tree whose nodes are integers, left subtree's (let's call it L) nodes are multiples of (at least one) right subtree's (R) node(s). I only require ...
9
votes
3answers
1k views

Why is a (collision-less) hashtable lookup really O(1)?

Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for. My question is: why is collision-less ...
120
votes
6answers
51k views

What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
0
votes
1answer
216 views

Bottleneck TSP with MST

There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far. ...
1
vote
1answer
35 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after ...
1
vote
2answers
43 views

Is there a known, fast algorithm for counting all subsets that sum to below a certain number?

I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum: Given a set of integers, $S$, and a target number, $n$, what is the ...
8
votes
2answers
172 views

Is integer sorting possible in O(n) in the transdichotomous model?

To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem: Given a sequence of length $n$ consisting of finite integers, find the permutation where every ...
2
votes
1answer
3k views

Proving that if coNP $\neq$ NP then P $\neq$ NP

I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it. Let ${\sf coNP}$ be the class of languages $\{\overline{L}: L \in {\sf NP} \}$. Show ...
2
votes
1answer
83 views

Stronger versions of P != NP which better express actual convictions

Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy ...
0
votes
1answer
792 views

Showing that CLIQUE can be verified in polynomial time

The CLIQUE problem -- problem of finding the maximum clique in a graph -- is NP-complete. That is, CLIQUE is in NP and there is an NP complete problem, 3-SAT for one, that reduces to CLIQUE in ...
1
vote
0answers
36 views

Poly-time reduction from directed Hamiltonian Path to undirected HP, both with with known start and end

this is homework, so PLEASE do not give me the solution(!), but help me get there on my own. I've got to proof that directed Hamilton Path with fixed stard and ending and undirected Hamilton Path ...
0
votes
0answers
34 views

What is an example of a problem that is in NP - P, but not NPC? [duplicate]

Assuming $P \neq NP$, I expected that $NP - P \subset NPC$, but from the diagram on Wikipedia it appears to not necessarily be true. What is an example of a problem that is complex enough to be in ...
3
votes
1answer
39 views

Is the word problem for regular languages in ALogTime?

Given a regular language (by a sparse or dense matrix describing the graph of the NFA) (initially the description was supposed to be a regular expression) and a word, can the problem whether the word ...
10
votes
1answer
238 views

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets: If the set resulting from the union, intersection, or Cartesian product of two ...
0
votes
1answer
29 views

Reduction from 4COL to 3COL

I have a problem with following task: $4COL \in PTIME \Rightarrow 3COL \in PTIME$. Is there any elementary proof to do it?
13
votes
4answers
1k views

Teaching NP-completeness - Turing reductions vs Karp reductions

I'm interested in the question of how best to teach NP-completeness to computer science majors. In particular, should we teach it using Karp reductions or using Turing reductions? I feel that the ...
3
votes
1answer
47 views

Proving that if A⊕B ∈ NP then NP = coNP

I got this question: Let $A \oplus B = (A\cap \bar{B})\cup(\bar{A}\cap B)$. Proof that $NP = coNP$ if and only if $A,B\in NP$ and $A \oplus B\in NP$. But I don't know how to proof the ...
1
vote
1answer
28 views

NP-Completeness: A question about reduction and hardness [duplicate]

I am trying to understand the definition / meaning of reduction. Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq_{x} B$? For ...
0
votes
1answer
58 views

Does exponentiation reduce to multiplication or the other way around?

Is is more accurate to say that in complexity theory: $$\text{exponentiation} \leq_p \text{multiplication}$$ or $$\text{multiplication} \leq_p \text{exponentiation}$$ I understand that if we know ...
3
votes
1answer
56 views

How to show that a problem is easy?

Let $P$ be a problem that you need to study its difficulty, i.e., NP-hard, Polynomial-time solvable, etc. My question is: If I reduce a known polynomial time problem (say, maximum matching in ...
4
votes
1answer
243 views

Confusion about the Time Hierarchy Theorem and relativization

I know that $\mathsf{P}^A = \mathsf{EXP}$ for any $\mathsf{EXPTIME}$-complete language $A$. Is it true that $\mathsf{DTIME}^A(n^k) = \mathsf{EXP}$ for any fixed $k$ and any ...
0
votes
0answers
24 views

How to show that if a relativized PH collapses, then PH collapses itself

Let $A$ be an arbitrary set in PH. Suppose PH$^A$ collapses. I am now asked to show that PH itself must collapse. I have remarked that, since $A$ is in PH, $A$ must in particular be in one of the ...
1
vote
1answer
72 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
1
vote
2answers
26 views

How to argue about semi-decidability of a problem?

I have the following problem, and I try to prove that it is semi-decidable, but I have a hard time arguing about it. I know that if a problem $\mathcal{P}$ is semi-decidable, then we can build a ...
6
votes
1answer
63 views

Why is the probability used in the definition of RP complexity classes, arbitrary?

I was looking at the following wikipedia article on the RP complexity class: https://en.wikipedia.org/wiki/RP_(complexity) In its definition it states: If the correct answer is NO then it always ...
7
votes
3answers
174 views

Why are most (or all?) polynomial time algorithms practical?

I read an interesting comment in a paper recently about how weirdly useful maths turns out to be. It mentions how polynomial time doesn't have to mean efficient in reality (e.g., ...
0
votes
1answer
51 views

IF A is reduced to B and B belongs to NPC then where does A belongs to?

i came across a question with no proper explnation. IF A is reduced to B and B belongs to NPC then we cant say anything about A since it can be as harder a NPH and as easier as P. i know why it is as ...
6
votes
3answers
4k views

What is complement of Context-free languages?

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
4
votes
0answers
65 views

How to select a subset of items in two different sets such that their product is maximum?

Let $\mathbf{a}$ and $\mathbf{b}$ be two complex vectors in $\mathbb{C}^n$ and $\sigma$ a positive real number. Let $k$ be a positive integer less than $n$. Select a subset of $\{1,\ldots,n\}$, $S$, ...