# All Questions

49,088 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
1 vote
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 ...
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....
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
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 ...
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
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
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
329 views

• 111
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
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 ...
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
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
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 ...
1 vote
17 views

1 vote
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 ...
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 ...
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 ...

15 30 50 per page