Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

3
votes
3answers
74 views

number encoding effect on complexity

I started reading the book "Data Structures and Network Algorithms" by Robert Tarjan, which is a classic (but a bit outdated - 1983) and I am a bit perplexed by the paragraph in the first chapter, ...
3
votes
1answer
39 views

Reduction from PARTITION to MAX-CUT

I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT ...
1
vote
2answers
53 views

Question about the definition of complexity class oracles

If $B$ is a complexity class, then the class $P^B$ (for example) is defined as the set of problems that can be run in polynomial time, given an oracle to every problem in $B$. That's what they told ...
2
votes
1answer
38 views

NP-complete problems and sub-expenential sized circuits

If one were to show that an NP-complete problem had $2^{n^{O(1)/\log{\log{n}}}}$ circuit complexity, what would the consequences of this be?
0
votes
1answer
42 views

Time complexity of Dynamic Array via repeated doubling

When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the ...
-2
votes
1answer
49 views

NP hard: Mixed Q Horn SAT

Prove that Mixed Quantified Horn SAT problem is NP hard by reducing the Q3SAT problem to it. Q3SAT: 3SAT with possibly universally and existentially quantified variables. Mixed Quantified Horn ...
1
vote
1answer
52 views

To show that a graph-problem is in $L$ or $NL$

Consider the following problem: $$A=\left\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\}$$ $G$ is a directed graph. $s,t\in V$. There is a simple path from $s$ to $t$ (a simple ...
3
votes
0answers
50 views

Graph canonization is not a decision problem. But what type of problem is it?

I noticed that the most convenient way to deal with quotient structures (like the rational numbers or other equivalence classes) within ZFC is to select a unique representant from each equivalence ...
0
votes
0answers
25 views

Is the following statement on NP reductions correct [duplicate]

Since NP is closed under polynomial-time reduction, any problem $A \in NP$ can be reduced to a problem $B \in NP$.
1
vote
1answer
58 views

Proving DPATH is NP-complete by a reduction from HAMPATH

I have a language DPATH that I'm trying to complete is NP-complete. ...
0
votes
2answers
67 views

Using induction to prove a big O notation [duplicate]

I'm trying to prove that the following recurrence relation has a runtime of O(n): fac(0) = 1 fac(n+1) = (n + 1) * fac(n) ...
0
votes
1answer
34 views

Demonstration that every finite set is computable [closed]

What is the best demonstration that show that "Every finite set is computable"? thanks
1
vote
1answer
88 views

RSA encryption why does ed=1?

So I fully understand the how the RSA algorithm works, but now I am trying to reason with the formula. I want to know: why the public key e and the private key d in the RSA encryption have to ...
0
votes
0answers
23 views

Can P vs NP be independent of accepted axioms? [duplicate]

On wikipedia's page on P vs NP it says that think that of 151 researchers surveyed, their thoughts were as follows: "126 (83%) believed the answer to be no, 12 (9%) believed the answer is yes, 5 ...
3
votes
4answers
867 views

How to prove that problem is not in P

Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis?
10
votes
1answer
328 views

Computational complexity vs. Chomsky hierarchy

I'm wondering about the relationship between computational complexity and the Chomsky hierarchy, in general. In particular, if I know that some problem is NP-complete, does it follow that the ...
1
vote
1answer
59 views

How to show that FPATH is in NL?

Consider this problem: $\qquad\displaystyle \mathsf{FPATH} = \{\langle G, a_1,\dots,a_n\rangle \mid G \text{ is a digraph with directed path } (a_1,\dots,a_n)\}$ It's allowed to visit nodes outside ...
2
votes
1answer
32 views

A variant of the set cover problem: Is that a known problem?

Can this problem be solved in poly time? Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$. Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that ...
5
votes
0answers
75 views

research on OR and AND compression in SAT formulas

this is a new/advanced paper on OR and AND compression of SAT formulas, a newer area of research that seems not covered in any textbooks so far. A simple proof that AND-compression of NP-complete ...
1
vote
1answer
61 views

Set of $\mathsf{NP}$-hard languages closed under set inclusion?

As the title says, my question is whether the set of $\mathsf{NP}$-hard languages is closed under set inclusion, i.e. whether for any $\mathsf{NP}$-hard language $L$, all subsets of $L$ are also ...
3
votes
1answer
79 views

Simplest argument that language decidable in constant time cannot be $\mathsf{NP}$-hard?

My question is specifically about $\emptyset$, but more generally about any language that can be decided in (deterministic or nondeterministic doesn't really make a difference here) constant time. ...
0
votes
0answers
18 views

TFNP and #P relation

Is there any known relationship between the complexity classes TFNP and #P. On first sight, it seems we can not compare them. Is there any work done either about this question, or about something ...
1
vote
0answers
20 views

Upper bounds for $NP$ based on $NEXP = EXP$

It's open whether $EXP = NEXP \to P = NP$ (the other direction can be shown by padding). My question: has there been any progress along these lines at all? For example, can we show that $EXP = NEXP ...
1
vote
1answer
28 views

comparisons vs arithmetic complexity

I'm trying to find out which operation is fast, evaluating a comparison vs doing an arithmetic option on a single word (e.g subtract, add). Can anyone point me in the right direction with some blogs, ...
1
vote
3answers
62 views

NP-completeness: Reduce to or reduce from?

Very simple question, but a mistake I make often enough that I'd love to have a standard reference. I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve ...
0
votes
0answers
26 views

The time complexity to find the largest rising left-neighbourhood for every element in an sequence? [duplicate]

For example, in sequence 3, 4, 3, 2, 4, the largest rising left-neighbourhood for 2 is 4 3 2 ...
0
votes
1answer
36 views

Reduction from partition to multiprocessor scheduling

I am kind of unsure about a reduction between two problems. Here are the two problems: PARTITION: Instance: A finite set of n positive integers $S= \{a_1,a_2,...a_n\}$. Question: Can the set $S$ be ...
1
vote
0answers
19 views

Grover algorithm for known number of solutions

I am reading Computational Complexity book and specifically Grovers search algorithm. I am aware that if we knew in advance exact number of solutions $K$, then the basic algorithm can be tweaked to ...
1
vote
1answer
36 views

What is the difference between turing reductions and many-one reductions?

To show that a particular language $A \in C$ is $C$-complete, where $C$ is some complexity class, we might construct a reduction from some known $C$-complete language $B$ to $A$, where $B$ is ...
3
votes
0answers
58 views

What are appropriate isomorphisms between formal languages?

A formal language $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$, that is, a set of words over that alphabet. Two formal languages $L$ and $L'$ are equal, if the corresponding sets are ...
4
votes
1answer
115 views

Complexity of bitwise AND operation on bit string regular expressions

Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time ...
3
votes
3answers
305 views

Can't understand why the DP Subset Sum algorithm is not polynomial

I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
-1
votes
1answer
41 views

NP hardness of Partition

I'm trying to show that PARTITION is NP-hard. I'm not sure if what I have is correct so I'll write what I have. I tried to reduce it from SUBSET_SUM: $$PART= \{S\subset\mathbb{Z}|\exists C \subset S: ...
0
votes
1answer
33 views

Is polynomial time reducibility reversible?

If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$? My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to ...
0
votes
1answer
195 views

NP Completeness of 3-SAT problem [closed]

I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the ...
1
vote
1answer
65 views

Why is the set of NFA that accept all words in co-NPSPACE?

In Sipser's book there is a section describing how to decide $\qquad\displaystyle \mathrm{ALL}_\mathrm{NFA} = \{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^*\}$ in polynomial space. ...
2
votes
1answer
110 views

Are there any PSPACE problems that don't exist in NP-Hard?

The question is in the title, I suppose. I am studying complexity classes, and I understand that NP-Hard is the set of problems that are at least as hard as the hardest problems in NP. Therefore, it ...
1
vote
0answers
11 views

Is it possible to do reductions with non-decision problems? [duplicate]

I've recently begun studying reductions in my algorithms class. All the reductions I've seen have been from decision problem $\to$ decision problem. Is it possible to do reductions with non-decision ...
3
votes
1answer
53 views

Complexity of factoring products of distinct prime numbers

Problem: Input is an integer number $x$ that we know factors as $p_{i_1}\cdot p_{i_2}\ldots p_{i_n}$, where the $p_{i_j}$'s are distinct prime numbers. Output is the above factorization of $x$. Do ...
1
vote
1answer
19 views

How to find partition set of a Partition Problem using its decision problem

I understand Partition Problem is NP-complete. Given we have a magic black box that can answer Yes or No for the partition problem. I was wondering how to come up with a polynomial time algorithm to ...
3
votes
2answers
221 views

are NP Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. ...
1
vote
3answers
213 views

Is the class NP closed under complement?

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
0
votes
1answer
34 views

How does one figure out where a class of languages falls under some complexity class? [closed]

I was wondering how can someone prove that one class of languages is of a certain complexity? For example, how could I show the Turing-recognizable languages are in P? Would I have to come up with ...
3
votes
1answer
53 views

How can I identify that a restricted variant of Boolean SAT remains hard or not?

While I was studying SAT problem and its different instances, in Algorithms for the Satisfiability (SAT) Problem: A Survey by J. Gu et. al PDF, I came up with this variant (not mentioned there, but I ...
6
votes
1answer
444 views

How do we know any problem is in NP-complete if we don't know all problems in NP?

A problem is NP-complete if: It is in NP. All problems in NP can reduce to it. It's number 2 that I'm concerned with here. I would be highly surprised if we knew every problem in NP. Based on ...
2
votes
1answer
25 views

Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities?

So both the 0/1 subset sum problem (find a subset of given numbers that add up to a target sum) and the subset sum problem with "multiplicities" (find non-negative integer coefficients for the set ...
7
votes
1answer
124 views

NP Problems with unique solution

Is there any class of NP problems that have one unique solution? I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
4
votes
1answer
57 views

$NP\subseteq TIME[O(n^{\log n})]$

Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.
0
votes
1answer
32 views

Maximum number of configurations on a TM that decides the language $A_\text{NFA}$ [closed]

Consider a Turing Machine $M$ that decides the following language: $$A_{\text{NFA}} = \{ \langle N,w \rangle | N\text{ is an NFA and }N\text{ accepts }w \}.$$ Based on its input size, if $M$ wants to ...
1
vote
2answers
50 views

Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?

Let the following datatype be defined: data T = A | B T | C T T That is, B, B T, B (B T), C A A, C (B T) A and so on all are ...