All Questions
49,088
questions
1
vote
1
answer
90
views
Why does problem F belong to PSPACE?
In the following graph, each node represents a computational problem. An arrow like A -> F indicates that there is a polynomial time Karp reduction from A to F. Observe that there could be more ...
- 13
0
votes
1
answer
30
views
Smallest sum not obtainable using a subset of elements in array greater than the minimum element
I am solving a variation of the missing coin sum problem, modified to be as follows:
You have n coins with positive integer values. What is the smallest
sum greater than the minimum coin in the array ...
- 133
1
vote
2
answers
53
views
Is this LTL formula really valid?
Fp → (¬p U p)
What if I have a transition system in which p is always true? Then Fp would be valid but not (¬p U p), right?
This formula is claimed to be valid in my study litterature, what have I ...
2
votes
2
answers
105
views
Can a universal worst case problem instance exist?
Given a specific type of problem like sorting a list and a particular algorithm like insertion sort, I am aware that a particular instance of the problem is worst case complexity for the algorithm (i....
0
votes
2
answers
54
views
prove AP-SUM is NP-complete
EDIT: I had a translation error. Instead of "unuary", it's binary.
AP-SUM is the language defined in the following way:
A word in the language AP-SUM is a pair <S, t>,
so that S is a ...
- 111
0
votes
8
answers
1k
views
Why do computers use binary numbers in IEEE754 fraction instead of BCD or DPD?
I asked a new question because it more accurately reflects what I asked: about:Why don't decimal-floating-point numbers have CPU level support like float point numbers in usual computers?
I will ...
user173333
0
votes
1
answer
20
views
Complete language in P∪{C,D}
given: C is a NP-coNP language, D is a coNP-NP language and P is the known time-complexity class.
assumption: NP ≠ coNP.
I need to determine if exists a language B, such that:
a. B ∈ P∪{C, D}.
b. for ...
- 111
0
votes
1
answer
47
views
The number of words that M doesn't accept is finite
I need to show that the following language isn't Turing recognizable:
$$\text{COFINITE}_{TM} = \{\langle M \rangle | M \text{ is a TM and } \overline{L(M)} \text{ is a finite language}\}$$
but I keep ...
- 111
0
votes
2
answers
25
views
Calculating the Maximum Speedup for a Program with Sequential and Parallel Components
A program $P$ consists of two methods: one sequential, which takes $ n + 15050 $ seconds to execute, and another that can be parallelized with full efficiency, taking $\frac{n^2}{100p}$ seconds, where ...
- 1
3
votes
1
answer
329
views
Minimum number of oracle call to solve Simon problem by a (NDTM) non-deterministic Turing machine?
Simon's problem is a computational problem used to demonstrate an oracle separation between BQP and BPP classes.
It is known that the minimum number of oracle calls to be made by the BQP machine is $\...
- 141
1
vote
1
answer
27
views
Variant of the k-MST problem on directed graphs?
Consider a weighted directed graph G and a special node $u$ in $G$. Are there any complexity results and algorithms on finding a minimum-weight directed acyclic subgraph $S^*$ of $G$ that contains $u$ ...
- 23
-1
votes
0
answers
18
views
Creating a matrix that its ij element is the number of times an ij element of a second matrix is larger than the elements of a third matrix
I have two n-by-m matrixes $M1$ and $M2$. I want to create a new n-by-m matrix $M3$ such that the $ij$ element is $M3_{ij} = \sum_k \sum _l 1(M1_{ij} > M2_{kl})$. Is there a way to do it without ...
- 21
1
vote
1
answer
96
views
set of words w such that M halts on w is decidable
I need to prove that the language following language is not turing-recognizable:
$$\text{dec-haltTM} = \{ \langle M\rangle: \text{$M$ is a TM and the set of words that M halts on is decidable}\}$$
I ...
- 111
-1
votes
0
answers
21
views
Regarding finding if recurrence is linear or not
The question is to check if the given recursion tree is linear or not. I was able to find check if the recursion of the options above g using recursion tree method, but I am unable to check for the ...
0
votes
1
answer
32
views
Unusual language in NP
Under the assumptions $\text{NP} \neq \text{coNP}$ and $\text{P}\neq\text{NP}\cap \text{coNP}$, we need to prove that
there is a language $L$ that satisfies the following:
$L\notin \text{P}$.
$L\in \...
- 111
0
votes
0
answers
10
views
Why does it satisfy the definition of a subgradient vector in a flow network problem
Hello everyone, I need to clarify some doubts. I was reading the article 'Subgradient Optimization Methods in Integer Programming with an Application to a Radiation Therapy Problem.' This is my first ...
- 1
1
vote
1
answer
147
views
What is the connection between a regular language's pumping number, and the number of states of an equivalent deterministic automaton?
I am self-studying Automata and Formal Languages from a set of past lecture notes, and I have a question about the proof of the Regular Pumping Lemma. The proof defines $D$ to be a deterministic ...
-2
votes
1
answer
37
views
How could "the mind" be uncomputable if it's due to neurons processing information?
This is going to be a very naïve question:
Some biologists, physicists and computer scientists say that what our brain does (generally speaking "the mind", including our thoughts, our ...
- 105
0
votes
1
answer
43
views
How to show $NP^{BQP} = QMA$?
I am currently reading the below document authored by @Lieuwe Vinkhuijzen.
In equation 2.1 (page 14 of this), the below equation is mentioned.
$${\Sigma}_1^{BQP} =NP^{BQP}= QMA$$
$NP$, $BQP$, and $QMA$...
- 141
2
votes
2
answers
33
views
How does the Goldreich-Levin Theorem imply the existence of secure pseudorandom generators?
I am reading the text "Computational Complexity, A Modern Approach". On pg183 it is explained how the Goldreich-Levin theorem implies the existence of a secure pseudorandom generator. The ...
- 31
1
vote
0
answers
17
views
Optimally sampling edge weights on a graph
I am working on some network problems where we do not know the underlying edge weights on the network precisely. All we know is that for a (directed) edge $(u,v)$ in the network, the weight $w(u,v) \...
- 23
-1
votes
0
answers
14
views
How to translate a virtual address to physical?
I have encountered the following question in an exam. I've checked all the lessons and notes there are of this class and I've found nothing.
Question:
In a paginated memory management scheme we have ...
- 1
4
votes
1
answer
58
views
Detecting/removing thin sections of polygons
Given a non-self-intersecting polygon made of straight segments how do you detect/trim sections of the polygon that are "thin"?
If an algorithm exists for this, then great! If not, then...
...
0
votes
1
answer
39
views
Balancing players into two teams
I'm trying to find an algorithm which would arrange ranked players into 2 teams automatically before the game starts in a balanced way.
The game has 2 teams, each team can have up to 5 players, and ...
- 103
0
votes
0
answers
10
views
Escaping the cycle: Route planning in graphs with conditional edges
Given a directed graph $G(V, E)$, I want to find a route, $R \in E^*$ from $S$ to $T$ for $S,T \in V$. If $G$ includes a cycle, how can I find a route that includes $n$ iterations of the cycle before ...
1
vote
1
answer
58
views
Give a class of languages which is closed under intersection and union, but not under complement
I am pondering this question, it is posed early on in a course on Formal languages and Automata, but before much progress has been made on closure of Regular and Context Free languages under ...
2
votes
0
answers
30
views
What's the proper name for combinator λ x . λ y . x (x) = S(S(K(S))(K))(K)
What is the proper name for combinator
$$λ x . λ y . x (x) = S(S(K(S))(K))(K) \text { ?}$$ I call it dbl and I noticed that it's half a quine.
But I would like to ...
- 121
1
vote
0
answers
28
views
Construction of a polynomial time algorithm
We are currently learning derandomization, which aims to transfer a probabilistic proof into a deterministic algorithm. My problem is as follows.
Given $n$, constructs in time polynomial in $n$, a ...
- 11
2
votes
1
answer
467
views
What role does the lower bound play in the statement of Savitch's Theorem?
Savitch's Theorem states that $\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$ for any function $f\in \Omega (\log(n))$.
I don't ...
0
votes
0
answers
16
views
Which restrictions of SMT problems are decidable and what is their complexity?
We can easily create a SAT solver that is guaranteed to halt with "SAT" or "Unsat", by simply enumerating all possible solutions. Afaik, SOTA SAT solvers like ...
- 4,062
0
votes
1
answer
28
views
Proving Non-Semi-Decidability of Language L - Seeking Reduction Strategy
I'm working on a problem involving the language
𝐿 =
{
𝑤
∣
time𝑀𝑤
(
𝑥
)
≤
∣
𝑥
∣
+
1
for all words
𝑥
}.
The language consists of words
𝑤 where the Turing machine
𝑀𝑤 halts within
∣
𝑥
∣
+
1
...
- 1
1
vote
2
answers
37
views
Complexity of checking validity of downscaled game of life
This is a question I thought up. I'm quite confident the answer is NO, but I'm not sure how to show it, and I'm wondering if this is known.
Imagine you are given a video of a 2k by 2k grid of bounded ...
- 111
1
vote
0
answers
21
views
Find a basis of a vector space minimizing the numbers of nonzero coordinates for a bunch of vectors
I've got a (to be a bit specific) 84-dimensional rational vector space, and as many as 1197 vectors in it. In the basis of the space that I've got, numbers of nonzero coordinates for these vectors ...
- 111
2
votes
1
answer
24
views
Complexity of deciding if a DFA is counter-free
It is well-known that deciding whether an NFA or a regular expression define a counter-free/star-free language is PSPACE-complete.
Does the problem become easier if I have a DFA as input? What's the ...
- 548
1
vote
1
answer
160
views
Can this Integer Linear Programming problem be solved in polynomial time?
I have $n$ binary variables, and $m$ constraints. Each constraint can be stated as: "exactly $b$ of the variables in $S$ are equal to 1", for some positive integer $b$ and subset of the ...
- 13
0
votes
0
answers
25
views
Is `f.splitting_field()` a one-way function candidate?
Is computing the splitting field of a polynomial a candidate for a one-way function?
Let $K$ be a number field and $f, g \in K[x]$. Let L_f = f.splitting_field() ...
- 133
1
vote
0
answers
18
views
What is the computational complexity of finding the splitting field of a polynomial?
Suppose $K$ is a number field and $f \in K[x]$ is irreducible. What is the computational complexity of computing f.splitting_field()? I'm also interested in the ...
- 133
0
votes
1
answer
26
views
Recurrence relation simplification
I have initial condition $𝑛_1=2, 𝑣_1=1$, and the given recurrence relations: $𝑛_{𝑖+1}=2𝑛_𝑖,$ $𝑣_{𝑖+1}=2𝑣_𝑖+\frac{1}{2} 𝑛_𝑖$
I need to show that that,
$v_i=\Theta(n_i\log n_i).$
I observe ...
- 113
2
votes
1
answer
30
views
Generalizations of integer-programming for the polynomial hierarchy?
Integer programming is known to be NP-complete. We also know that each class in the polynomial hierarchy contains elements not contained in the ones below, so Integer programming is not complete for ...
- 4,062
0
votes
0
answers
50
views
Help with writing an algorithm
I'm not sure if this question fits the forum, and I should mention that I'm not a computer scientist at all—just a regular normal boy with very little coding knowledge.
But I wanted to ask if it's ...
- 1
3
votes
0
answers
40
views
How to Prove following Weighted Forest Problem is NP-hard?
I am studying the following Weighted Forest Problem, which is an optimization problem in graph theory focused on finding optimal forest structures in robust scenarios. The problem is defined as ...
- 31
1
vote
1
answer
64
views
How to make a NAND gate with vaccum tubes?
We all know the NAND gate with mosfets. However, a lot of history of computers is unknown. Can you please let me know a diagram of a NAND gate with mosfets how is it made with vacuum tubes or a ...
2
votes
1
answer
171
views
NP-Hardness: Finding the Best Subtree for Hierarchical Matching in Elasticsearch
Given a graph G = (V, E) (a forest) stored in Elasticsearch and a set of requests R, where each request r in R can potentially match between 0 and V vertices in G, the task is to identify the "...
- 21
1
vote
1
answer
23
views
How does the RETE algorithm for expert production systems work?
I struggle with the understanding of this algorithm. Is there anybody willing to explain me how the tree is built in RETE and how it helps with concrete inputs?
- 111
2
votes
3
answers
147
views
How to simplify $O(\log (n!))$?
I have a problem with this time complexity: $\log (n!)+\frac{5}{2}n\log\log n$. I'm not sure how to deal with the $n!$ term. I know from calculus class that the sequence $n!$ is bigger than any ...
- 31
2
votes
2
answers
235
views
Solving the "Reverse" Assignment Problem with an Added Constraint?
Note: This is a continuation of my previous question, found here
As written, my previous question was too unconstrained: @BaderAbuRadi showed that depending on the $C$ chosen, there can be multiple ...
- 55
1
vote
0
answers
15
views
Is it possible to start a Dijkstra search from a source node s, bounded at r, with a non-empty distance map and priority queue?
TL:DR: I want to know whether correctness is affected if I start Dijkstra with a distances map that already contains shortest paths shorter than $r$ and a priority queue initialised with those ...
- 11
1
vote
1
answer
42
views
Find the number of sink nodes per source node efficiently
My task is to write a function that, given a source nodes of a graph, returns the number of sink nodes (nodes with no outgoing edges) it reaches. The only access I have is to retrieve the neighbors of ...
- 13
2
votes
1
answer
29
views
Shortest path to all nodes from a center point, repeats allowed
I'm trying to create an algorithm to figure out a path visiting every single node in a graph (undirected and unweighted) - similar to the traveling salesman problem, but I can visit a node multiple ...
- 21
0
votes
0
answers
18
views
How to enumerate theories logically equivalent to natural deduction?
Natural deduction seems to generally be structured around the idea of (an/) introduction and elimination rules(s) for each logical symbol.
I heard that that was an attempt to capture the way humans ...
- 140