Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

0
votes
0answers
20 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
26 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 ...
2
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, ...
1
vote
1answer
33 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
45 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 ...
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
199 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$ ...
2
votes
1answer
90 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
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 ...
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
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 ...
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$ ...
4
votes
0answers
75 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? ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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., ...
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$, ...
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 ...
1
vote
0answers
50 views

Sort complexity in a random array

if I have an unsorted array with the length of $10^6$, which is filled with absolutely different float numbers, which sorting algorithm would be the best to use and why? And which one would be the ...
3
votes
1answer
74 views

Proof that this problem is in NP

I have to prove the following problem is in NP (and define verifier as well as the certificate/witness): The input is a set of $n$ boxes with weights $w_{1},\ldots,w_{n}$ and two numbers $s$ and $t$ ...
1
vote
1answer
57 views

Which types of mathematical functions are the least complex for a computer to compute ?

Let's consider these four function types : Polynomial, Exponential, Logarithmic and Trigonometric. Considering that both input and output values are floating point numbers. How do they rank in ...
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 ...
0
votes
0answers
23 views

Is there a general form of polynomial reductions in complexity theory? [duplicate]

While reading Sipser, in computability I read about many to one mapping reducibility and Turing reducibility,the latter one being a more general form of reducibility. But in the introductory chapter ...
-1
votes
0answers
38 views

Conditions on randomized reductions

Supposing we have a problem $\Pi$. Suppose $\Pi$ has a randomized reduction from $\mathsf{3SAT}$ but there is no deterministic reduction then it is clear $\mathsf{NP}\neq\mathsf{P}$. My query is ...
2
votes
0answers
50 views

Proving that AM contained in Pi_2

i think that it's true that AM is contained in $\Pi_2$ but I'm not sure how to prove it. How do I prove that $AM \subseteq \Pi_2$?
3
votes
1answer
74 views

Different characterization of $\Delta_2^P$

$\Delta_2^P =P^{NP}$, is the set of all languages decidable by a polynomial Turing machine with access to a SAT oracle. I came across a definition of $\Delta_2^P$ as the set of all languages $L$ such ...
5
votes
0answers
113 views

complexity of a Constraint Satisfaction Promise Problem

Due to curiosity regarding possible extensions of Schaefer's dichotomy theorem, I wound up considering the "promise constraint" with 3 boolean inputs that's given by $C(x,y,z) ​ ​ = \hspace{.1 ...
4
votes
1answer
67 views

An obvious approach to explaining NP != coNP, how far has it been pushed?

A recent question made me think about an obvious approach for circumventing the "algorithm is allowed to do anything" problem, when proving lower bounds. Instead of starting with a simple looking ...
2
votes
1answer
105 views

An obvious approach to NP = coNP, is there a counterexample?

Let's try to solve "co3SAT" with an NTM in polynomial time. It seems we need, more or less, to guess a proof that the formula is unsatisfiable i.e. derive a contradiction. We've got a formula in ...
2
votes
1answer
62 views

2 SAT variants complexity class

Question: Which of the following languages are in P? which in NP? other classes? a. EXACTLY-2-CNF (every clause in the formula has 2 differenet literelas)- does there exist a satisfying assignment ...