# All Questions

48,990 questions
Filter by
Sorted by
Tagged with
30 views

### Algorithm to show that CFGNotAll is recursively enumerable

The task is to create an algorithm that shows that the problem CFGNotAll is recursively enumarble. CFGNotAll is defined as: Given a context free grammar G in CNF over the alphabet {a,b} with Variables ...
21 views

### L in NP and L is coNP-hard=>NP = coNP

How can I prove this: given this 2 sentences 1 <=> 2: There exists a language L ∈ NP that is coNP-hard. NP=coNP. the direction from 2 to 1 I can prove using the concept of NP-cpmplete and etc. ...
27 views

### Isn't the first requirement for NP-completeness redundant?

I am kinda learning but now that i have studied a lot about complexity theory, isn't the fact that if a problem in NP is Karp-reducible to a problem A then that means A is in NP too, so why do we need ...
1 vote
21 views

### Linear time algorithm for computing radius of membership hyper-sphere

We are given a Graph, G(V, E), where V is the node set and E is the edge set consisting of ordered tuples (u, v). The graph is undirected, as such, if (u,v) is in E, then (v, u) is in E. Alongside the ...
• 111
36 views

### Finding the maximum number of courses one can taking fewer than $k$ courses at a time

I bumped into this problem (in Spanish), bu Jon Ander Gómez y Alberto Verdejo. It boils down to: You are given a list of $n$ online courses ($1 \leq n \leq 10^3)$, each course $i$ defined by the ...
• 263
1 vote
37 views

### Efficiently sampling $k$ elements from the powerset while avoiding space blow up

Is there a way that I can space efficiently sample $k$ elements from $\mathcal{P}(\{1,2,\ldots, n\})$ without replacement? For instance, the naive approach would be as follows in Python: ...
• 244
91 views

### Is this "binary submatrix sum equation" problem NP-hard?

There is an unknown matrix $A$ of $R$ rows and $C$ columns. The entry at the $r$-th row, $c$-th column is $A_{rc}$. The matrix is a binary matrix, i.e. each entry is either 0 or 1. Another matrix $B$ ...
• 498
48 views

### Is garbage state necessary in DFA that enforces a particular input combination?

If I have the regex 1(0+1)* for example, then should my DFA have an arrow leading away from the starting state for when the first input is 0? I see that this regex ...
• 87
221 views

### Is it possible to have intersection of L1 and L2 DFA contain states with no input edge?

I am doing a HW problem where I have L1 and L2. I did the product construction method to produce all the new states of the DFA representing L1 and L2 (the number of states in L1 times the number of ...
• 87
1 vote
63 views

### How bad re-hashing can cost?

Lets assume that the load factor of a hash table of size $n$ became inappropriate. The process of re-hashing involves choosing a new hash function. A good choice of a new function will make the cost ...
• 147
24 views

### 4COL problem with additional constraint on the size

The task is to prove that that 4-coloring of a graph with additional constraint about number of vertices is NP-complete. Constraint: Each color class should contain at least $\frac{1}{5}$ of total ...
• 61
1 vote
39 views

• 73
30 views

### Is it possible to use a non-Turing-complete language to describe the steps to build a Turing Machine?

First of all, it is impossible to use a Turing-incomplete language to simulate a Turing-complete one (see link) However, is it possible to use a Turing-incomplete language to describe the steps to ...
• 111
1 vote
29 views

### Extract dominant value per column with single value per row in a matrix

Given a matrix $A \in \mathbb{R}_{+}^{n \times m}$ where $m \geq n$. I want to convert it into a form where there is a single $1$ per row yet no more than a single $1$ per column. The logic is convert ...
• 13
41 views

### What is the most efficient non-quantum computer that can be built?

I am aware of two models of computation, neither of which describe the optimal computer we can build: Turing machine: This model is not optimal due to the head having to travel a large distance ...
44 views

### Finding maximal elements of a partially ordered set

My problem Given a partially-ordered set $(S, <)$, I want to compute the set of maximal elements $$S_{max} =\{a\in S | \nexists b \in S, a < b \}$$ while making as few comparisons as possible ...
• 73
36 views

### Should a PDA reject words not in language?

Let's say we want to construct the PDA for the following language: $$L_4 = \{w_1bw_2 | w_1, w_2 \in \{a,b,c \}^* \ and \ (\#ab\in w_1) = (2 \times \#c \in w_2)\}$$ Let's consider the following PDA ...
• 111
1 vote
57 views

### How to determine whether two recursive data types overlap

I am working on a type system that supports recursive data types, e.g.: type a = (a * integer) | integer type b = integer would be valid type declarations, where <...
819 views

### Does a publication similar to the American Mathematical Monthly exist in Theoretical Computer Science?

I'm a math major who's been reading up on computational theory and automata theory and I think that I would love to learn more about these and other sub-fields in Theoretical CS. I'm pretty sure the ...
53 views

### O-notation confusion

I'm reading CLRS and I can't understand this part: in n-100<=c why we can't choose 101 for n (and more) and any value of c that's >=1?
91 views

### $f(n)=n^{100}$, $g(n)=2^{n/100}$, determine whether $f=O(g)$

I am reading Arora and Barak's book "Computational Complexity: A Modern Approach". I am doing EXERCISE 0.1.(b): $f(n) = n^{100}$, $g(n)=2^{n/100}$, determine whether $f=O(g)$. Here's what I ...
1 vote
42 views

### Proving $f(n) = 1 + c + c^2 + \cdots + c^n = \Theta(1)$

How can I prove that the function $$f(n) = 1 + c + c^2 + \cdots + c^n$$ is $\Theta(1)$ when $c<1$? where $n \in \mathbb{N}$ and $c \in \mathbb{R}$, with $c>0$. Can I use limits? Thank you in ...
• 11
53 views

### Is Calling a Function a Side Effect

I've noticed a pattern in trying to make functional programming effective - there is still some kind of impure, effectful operation going on, but it gets holed up in a single, manageable imperative ...
• 101
34 views

### Clever algorithm for ordered compact sub-grouping

I have a set of 2D points (called "seats"), with each having a scalar numerical value attached to it. I have an ordered sequence of groups, each with an integer attributed to it, such that ...
• 101
31 views

### Are there any ways to reduce the space complexity of the simplex method when dealing with totally unimodular (TU) matrices?

I am try to solve a problem with a strict space complexity and time complexity(60mb and 1s). I use the simplex method, but it requires significant space complexity, reaching up to $O(nm)$. However, ...
16 views

### What is b-bit precision?

I'm looking at the BitNet paper on 1-bit models by Wang et al. In section 2.1, they write We further quantize the activations to b-bit precision I assume they mean quantize the activations to ...
• 123
1 vote
37 views

### Does modifying input space change space complexity?

The auxiliary space analysis that involves modifying the input array can lead to "unfair" situations. Examples: Consider that an algorithm that uses O(N) memory and does not need to ...
27 views

### Fit data to a lookup table

I have been looking for methods to fit 1-D data to a lookup table. In other words, there's no known function that is used as a model. For example in the plots below, the measured data (blue) is fit to ...
46 views

### File format for SAT competitions

The file format for SAT competitions is available online here: Rules of the 2011 SAT Competition but is defacto inaccessible because all browsers redirect to the non-existing address. Question: where ...
• 143
326 views

17 views

### Does a Moore Machine always require an output for start state?

My lecture notes show all moore machines as having an output even for q0, the starting state. This video shows a Moore machine without an output for its starting state. I understand that all Moore ...
• 87
113 views

### Deducing upper bound for Boolean Circuit size from well-known algorithms

Given an algorithm A for computing binary function $f$. Assuming that A runs in time $t(n)$, what could we say about the size of the minimal Boolean circuit C that calculates f? I think that it ...
• 231
35 views

### Given a TM $M$ Denote $L(M), L_{rej}(M), L_{non-halt} (M)$, Is $L(M)\in R$ implies $L_{rej}(M)\in R$?

Question: Given the following definitions for a Turing machine $M$: $$L_{rej}(M) = \{w \in \Sigma^* : q_0w \vdash_M^* uq_{rej}v\}$$ Basically, represents the language of words that $M$ rejects (i.e.,...
1 vote