Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,201
questions
1
vote
1
answer
117
views
How to prove that this problem is NP-complete (or NP-Hard)
I have the following data:
A set $V$ of tasks, the starting time $s_j$ of each task and the duration $p_j$ of each task.
A set $K$ of resource, each resource has an availability function $R_{k}$ ...
CommunityBot
- 1
2
votes
1
answer
43
views
Selecting a submatrix of a binary matrix NP hard?
I have the following problem and I am wondering if it is NP Hard or not.
Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$.
A ...
D.W.♦
- 152k
0
votes
0
answers
13
views
Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds
Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system:
1: Assume that initially the nodes have IDs of size $\log(n)$ bits
2: The root is ...
- 295
0
votes
0
answers
48
views
Why weakening rule doesn't increase the size of resolution refutation?
I am studying the complexity of SAT resolution refutation. There is a useful tool named weakening rule
The weakening rule:
B -->B ∨ C
says that from a clause B we can derive the weaker clause B ∨ ...
- 176
1
vote
1
answer
37
views
Why do simple Logical Gates have an Irrational amount of Bits?
Suppose $2$ bits are used to encode a message, A and B.
If you know $A$ is $1$, you have one bit of information.
If you know $A\land B$ is $1$, you have two bits of information.
If you know $A\land B$...
- 8,742
0
votes
2
answers
2k
views
In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?
Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
CommunityBot
- 1
0
votes
1
answer
30
views
On proving the uncomputability of Kolmogorov complexity by contradiction
I have seen a proof by contradiction for the uncomputability of Kolmogorov complexity. The idea the basically the same as in the proof for halting problem (i.e., there are cases that lead to Berry ...
D.W.♦
- 152k
2
votes
1
answer
267
views
Constructing equivalent (to a polynomial-time degree) decision problems from function problems
Let's say we're some function problem, $R \subseteq \Sigma^* \times \Sigma^*$, where $\Sigma = \{0, 1\}$ and some oracle $O_R$ that solves $R$.
Now, we're given some language, $L \subseteq \Sigma^*$ ...
D.W.♦
- 152k
0
votes
1
answer
26
views
Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions
Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that ...
CommunityBot
- 1
1
vote
3
answers
144
views
Is the number of NP-complete problems finite?
It should be straight forward to show that there are infinitely many NP-hard problems:
Proof:
Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and ...
- 21
1
vote
1
answer
65
views
Integrality gap and complexity classes
I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems?
In particular, is there a class of problems for which their integrality ...
- 4,161
2
votes
1
answer
139
views
Can protein folding destroy cryptography?
They say that protein folding is an NP-hard problem, meaning that if we could figure out how any protein folds, we could solve any NP problem in polynomial time. However, doesn't this basically ...
- 8,742
0
votes
3
answers
57
views
If X is poly-time reducible to Y and X is in P, then Y is in P
The answer I found on the Internet is false. But my argument is that if I know that X is poly-time reducible to Y, which means I can use Y as a sub-routine to solve X, i.e., if I have a blackbox of Y ...
- 1
1
vote
2
answers
166
views
Question about how can i determine if counting sort is the right option over other sorting algorithms
So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm.
Now i find that solutions for that ...
CommunityBot
- 1
1
vote
1
answer
64
views
Can we show that #3CNF is in FPTAS
If we have a deterministic algorithm $A$ such that $\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\#3CNF$? How can we show that $\#3CNF \in ...
CommunityBot
- 1
0
votes
1
answer
23
views
is this lanuage or it' complement not Turing-recognisable
K = {<J, a, b, c> : J is a Java program, a, b, and c are integer variables declared in J, and throughout the execution of J, a never has the same value as b and a never has the same value as c}.
...
- 2,621
1
vote
1
answer
28
views
Can I reduce from the recognition version of one probem to another without knowing the exact parameter?
I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(...
CommunityBot
- 1
0
votes
0
answers
7
views
Impact of $P=BPP$ on $AM$ and $MA$'s relationship with non-interacting complexity classes? [closed]
In complexity theory the following is known:
$MA \subseteq AM$, $MA \subseteq S_2^P$, $AM \subseteq BPP^{NP}$ and $P \subseteq BPP$.
https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol ...
- 715
2
votes
2
answers
37
views
Can you enumerate the set of all words over a finite alphabet?
Can you enumerate the set of all words over a finite alphabet?
- 1,617
0
votes
2
answers
54
views
Can all NP-complete problems be reduced to NP?
I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around?
Can all NP-Complete be reduced to NP problems?
My understanding is ...
- 21
1
vote
0
answers
30
views
Lower Bound on Parity of Boolean Functions
Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
- 13
1
vote
1
answer
105
views
What complexity class is this set of grammars? In between NL and P?
Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals ...
CommunityBot
- 1
0
votes
1
answer
30
views
If NP problems are decidable, and decidable is subset of turning recognizable which recognizer can understand them?
I think the best way to explain my question would be to have sextuple (regular, context-free,
Turing-recognisable, decidable, P, NP).were you fill out 1 for promblem which lies into that section, ...
- 370
0
votes
0
answers
23
views
Goldwasser-Sipser protocol, but when two sets are "close"
I know that Goldwasser-Sipser protocol is for the problem of determining whether a set $S$ is of size $N$ or at most $N/2$. So it can be used to separate some set $A$ from another set $B$, based on ...
- 111
1
vote
2
answers
67
views
Relation between algorithms and models
I have found this question some time ago. While reading it, I had a problem with understanding the following idea:
Question, part 1: Is one allowed to talk about the time/space bound of any algorithm (...
CommunityBot
- 1
1
vote
1
answer
87
views
optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$
I want to optimize an algorithm for calculating $g(n)=\sum^n_{k=2} p(\Omega(k))\Omega(k)$
where $$ p(n) =
\begin{cases}
1 &\text{if $n$ is odd} \\
-1 &\text{if $n$ is even}
\end{cases}$$
and ...
- 38.2k
0
votes
1
answer
19
views
Equivalence of echo state networks and DFAs/NFAs
Echo state networks are theoretically equivalent to DFAs/NFAs, but how would you use an ESN to parse a regular language? Would you just feed many different input strings, some from the language and ...
CommunityBot
- 1
7
votes
1
answer
1k
views
What is the complexity of theorem proving?
I'm learning some computer science and mathematics by myself. I know that proving theorems in ZFC is undecidable in general, but, is there a formal way to express how complex it is? Is it as complex ...
- 6,757
0
votes
1
answer
70
views
Enumerate all superincreasing subsequences
A sequence of positive real numbers S1, S2, S3, …, SN is called a superincreasing sequence if every element of the sequence is greater than the sum of all the previous elements in the sequence. E.g: 1,...
CommunityBot
- 1
0
votes
0
answers
17
views
Can someone please explain classes MA and AM (with an example)? What happens to AM in case of PH[2]=PSPACE?
I am trying to understand two player (prover-Merlin and verifier-Arthur) interactive proof complexity classes and had a few doubts.
As I understand, the classes $MA$ and $AM$ involve two players, ...
- 715
2
votes
2
answers
591
views
Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?
You are given $n$ lists. The $i$-th list contains $k_i$ subsets of $\{1, \ldots, m\}$. You are also given an integer $s$. You should decide whether it's possible to pick up exactly one element (that ...
- 38.2k
3
votes
0
answers
40
views
The Hidden Subgroup Problem under different mappings
The Hidden Subgroup Problem (HSP) is an extremely prevalent problem in quantum computation, especially for factorization in Shor’s algorithm.
The problem is stated
Given an oracle for some function, $...
- 31
3
votes
0
answers
117
views
Is there a class for optimization problems with polynomial-time-computable bounds?
An optimization problem can be described by two functions $f$ and $g$, such that:
$f$ is a binary predicate representing the constraints: $f(x,y)$ is True if the output $y$ is feasible for the input $...
- 5,894
1
vote
1
answer
16
views
What are the sizes of 'functions' and 'fields' in the context of input to a decision problem?
I can reduce 3-Sat to the following NP-Complete decision problem:
Let $S = ${0,1,...,s-1}, $D \subseteq S$ and $P$ be a multivariate polynomial in $n$ variables. Decide yes iff there exists $\vec x \...
D.W.♦
- 152k
3
votes
3
answers
216
views
Question about the Relativization barrier
Baker, Gill, and Solovay has shown in their famous paper, that there are oracles $A$ and $B$ with $P^A = NP^A$ and $P^B \not= NP^B$. So, one can't solve the $P$ vs. $NP$ Problem
with methods like ...
- 393
5
votes
1
answer
221
views
Weakest reduction for P-completeness
It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-...
CommunityBot
- 1
0
votes
0
answers
30
views
Hardness of the bin packing problem
I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that
$$
1 > a_1 \geq a_2 \geq \dots \geq a_n > 0
$$
The ...
1
vote
0
answers
20
views
Class of optimization problems whose decision versions are in P
NPO is defined to be the class of optimization problems whose decision versions are in NP.
I would like to get the complexity class of optimization problems whose decision versions are in P.
Is such ...
3
votes
1
answer
135
views
Does a problem remain tractable If a single discrete variable becomes continuous?
Let $\mathcal{F}$ be a family of pairs of the form $(A,b)$, where $A$ is an integer matrix and $b$ is an integer vector with the same number of rows. For every integer $k$, define $L(\mathcal{F}, k)$ ...
- 5,894
0
votes
0
answers
19
views
Does $PP\subseteq BPP$ imply $PP\subseteq RP$?
Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$? clarifies $NP\subseteq BPP\implies NP\subseteq RP$.
What about for $PP$? Does $PP\subseteq BPP$ imply $PP\subseteq RP$ and $PP\...
- 2,862
2
votes
1
answer
64
views
Finding maximum via sum oracle
Let $A$ be an array of real numbers with a unique maximum element, such that $size(A)=O(2^N)$. Assume that we have an oracle that can evaluate a sum over any subset of indices of $A$ in $O(1)$ time. ...
0
votes
1
answer
52
views
Understanding reductions and notation
I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
- 5,169
0
votes
0
answers
43
views
Why are polynomials a natural measure for easiness of computational problems? [duplicate]
We understand the exponential function to constantly grow, which we consider bad for a problem. By constantly growing I mean the ratio
$\frac{f(n+1)}{f(n)}$
never tends to 1, where $f(n)$ is the ...
1
vote
1
answer
35
views
What is the complexity class of counting Yes/No instances of an NP problem?
Let's say that I have an NP-complete problem such as the Clique Problem. Let's also assume that I have a finte set of graphs. What is the complexity of counting Yes/No instances?
More specifically let'...
CommunityBot
- 1
0
votes
1
answer
20
views
P/poly and dyadic oracle
If we let a language L in {0,1}* be dyadic if for each x in L, and each index i with xi = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with ...
- 353
0
votes
0
answers
13
views
Relativizations/Oracles for the BPP and RP complexity classes
If we consider the complexity classes RP and BPP, then to show RPBPP = BPPRP my first thought is we need to use some kind of majority voting to amplify our success probabilities. The issue is I don't ...
- 13
0
votes
0
answers
54
views
Finding a Polynomial Time algorithm for the 3-SAT Problem
Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause :
Ai = (xr $\lor$ xs $\lor$ xt)
where 1 $\le$ r,s,t $\le$n and ...
0
votes
1
answer
70
views
Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier
For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X
a1x1 + a2x2 + ... + ...
- 1
2
votes
1
answer
168
views
Is this path planning problem NP-complete?
Given N integers L1, L2, ... , Ln ,we have a robot that starts at (0,0) moves north on integer grid for L1 steps, then it either continues in its current direction or makes 90 degrees right turn then ...
- 26.4k
0
votes
0
answers
25
views
Envy-Free Allocation is NP-Hard
If we consider the class fair division problem where we have a set of $n$-agents and a set $M$ of $m$-items, where each agent has a valuation function defined on the set of items $$v_i : 2^m \...
- 31