1. All Categories
2. Computer Science

# Computer Science : Recent Questions and Answers

## Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

Assume for the regular knapsack problem we have additional information - maximal weight of every item - lets denote it as P. Using this information, I want to solve the...

## Number of words of length n for special language

Let $Sigma$ be an alphabet and let $L$ be a language over it with the following properties:if $win L$ then there exists $vin Sigma^*$ such that...

## Intuition for Church-Turing thesis for Turing machines

I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion --...

## Global-input-local-output p-time algorithms

Are there polynomial-time algorithms whose input is global but output is local in nature? What I have in mind is a problem instead of an algorithm. It’s the satisfiability (SAT)...

## Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

For example, a valid number would be 6165156 and an invalid number would be 1566515. I have tried many times to construct a finite state machine for this with no...

## Is $EVEN-SAT$ $NP$-hard?

I'm looking for an $NP$-hardness proof for the following variant of $SAT$: EVEN-SAT = {langle phi rangle: phi text{ has an even number of satisfying assignments}}...

Asked on 11/23/2021 by Zur Luria

## Proof of the undecidability of compiler code optimization

While reading Compilers by Alfred Aho, I came across this statement:The problem of generating theoptimal target code from a source program is undecidable in general.The Wikipedia entry on optimizing...

Asked on 11/23/2021 by Stephen Mwangi

## Algorithm suggestion to order data with specific condition

Suppose, we want to rearrange all possible $n$-bit binary strings (i.e., we have $2^{n}-1$ possible strings) in a 1-D array $X$; given that stings with smaller ...