About: Theories, proofs and computational complexity

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Theories, proofs and computational complexity Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Projekt, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	http://linked.opendata.cz/ontology/domain/vavai/Projekt
rdfs:seeAlso	http://www.isvav.cz/projectDetail.do?rowId=IAA1019401
Description	This is a purely tehoretical research in mathematics and theoretical computer science. The main aim is to study the concept of computational complexity from several points of view:1. first order tehories, 2. the propositional calculus and 3. voolean circuits. MOre specifically, we will study Bounded Arithmetic, the complexity of proofs in propositional calculus and various computational models. Furthermore, we shall investigate related questions in the foundations of mathematics and set theory. (en) Jedná se o teoretický výzkum v matematice a teoretické informatice. Hlavním cílem je studovat pojem výpočetní složitosti z několika hledisek: 1. teorii prvního řádu, 2. výrokového počtu a 3. booleovských obvodů. Konkrétně se jedná o studium omezené aritmetiky, složitosti důkazů ve výrokovém počtu a různých výpočetních modelů. Budeme zkoumat také související otázky logických základů matematiky a teorie množin.
Title	Theories, proofs and computational complexity (en) Teorie, důkazy a výpočetní složitost
skos:notation	IAA1019401
http://linked.open...avai/cep/aktivita	Grants of distinctly investigative character focused on the sphere of research pursued at present particularly in the Academy of Sciences of the Czech Republic
http://linked.open...kovaStatniPodpora	http://linked.opendata.cz/resource/domain/vavai/projekt/IAA1019401/celkovaStatniPodpora
http://linked.open...ep/celkoveNaklady	http://linked.opendata.cz/resource/domain/vavai/projekt/IAA1019401/celkoveNaklady
http://linked.open...datumDodatniDoRIV	2009-07-02 (xsd:date)
http://linked.open...i/cep/druhSouteze	VS - Veřejná soutěž ve výzkumu a vývoji
http://linked.open...ep/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open.../cep/fazeProjektu	69258836
http://linked.open...ai/cep/hlavniObor	BA - Obecná matematika
http://linked.open...hodnoceniProjektu	V - Vynikající výsledky (s mezinárodním významem apod.). Zároveň byly splněny cíle a předpokládané výsledky uvedené ve smlouvě / rozhodnutí o poskytnutí podpory.
http://linked.open...vai/cep/kategorie	ZV - Základní výzkum
http://linked.open.../cep/klicovaSlova	logic; propositional calculus; computational complexity; set theory (en)
http://linked.open...ep/partnetrHlavni	Matematický ústav AV ČR, v. v. i.
http://linked.open...inujicichPrijemcu	0 (xsd:int)
http://linked.open...cep/pocetPrijemcu	1 (xsd:int)
http://linked.open...ocetSpoluPrijemcu	0 (xsd:int)
http://linked.open.../pocetVysledkuRIV	68 (xsd:int)
http://linked.open...enychVysledkuVRIV	68 (xsd:int)
http://linked.open...lneniVMinulemRoce	2008-02-21 (xsd:date)
http://linked.open.../prideleniPodpory	http://linked.opendata.cz/resource/domain/vavai/cep/prideleniPodpory/IAA1019401
http://linked.open...iciPoslednihoRoku	2008
http://linked.open...atUdajeProjZameru	2009
http://linked.open.../vavai/cep/soutez	SAV02004-A
http://linked.open...usZobrazovaneFaze	DUU
http://linked.open...ai/cep/typPojektu	P - Projekt výzkumu a vývoje financovaný ze státního rozpočtu
http://linked.open...ep/ukonceniReseni	2008-12-31 (xsd:date)
http://linked.open...ep/zahajeniReseni	2004-01-01 (xsd:date)
http://linked.open...jektu+dodavatelem	Byly dokázány věty o důkazové složitosti výrokového počtu, o teoriích omezené aritmetiky a složitosti booleovských obvodů. Byly nalezeny nové algoritmy pro on-line rozvrhování a analyzovali jsme jejich složitost. (cs) Theorems about proof complexity of the propositional calculus, about bounded arithmetic theories and about the complexity of boolean circuits were proved. New algorithms for on-line scheduling and analyzed their complexity were found. (en)
http://linked.open...tniCyklusProjektu	ZBBBKU
http://linked.open.../cep/klicoveSlovo	logic computational complexity propositional calculus
is http://linked.open...vavai/riv/projekt of	Diagonalization in proof complexity The greedy algorithm for the minimum common string partition problem Functions that have read-twice constant width branching programs are not necessarily testable Twelve problems in proof complexity A proof complexity generator Forcing with random variables and proof complexity Logic for all willing to think On theories of bounded arithmetic for NC1 Consistency and games - in search of new combinatorial principles On Explicit Ramsey Graphs and Estimates of the Number of Sums and Products Online competitive algorithms for maximizing weighted throughput of unit jobs Frege systems for extensible modal logics The strength of sharply bounded induction An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequalityd Complexity of admissible rules On Independence of Variants of the Weak Pigeonhole Principle Substitutions into propositional tautologies NP search problems in low fragments of bounded arithmetic Consequences of the Provability of $NP /subseteq P/poly$ Approximate counting in bounded arithmetic Online scheduling of equal-length jobs: Randomization and restarts help On the complexity of cake cutting An Approximation Scheme for Cake Division with a Linear Number of Cuts Improved online algorithms for buffer management in QoS switches Improved online algorithms for buffer management in QoS switches KAM-DIMATA Series 2004-662 and ITI Series 2004-186. A simple combinatorial proof of duality of multiroute flows and cuts KAM-DIMATA Series 2004-659 and ITI Series 2004-182. Online scheduling of equal-length jobs: Randomization and restarts help KAM-DIMATA Series 2004-658 and ITI Series 2004-181. Improved online algorithms for buffer management in QoS switches KAM-DIMATA Series 2004-657 and ITI Series 2004-180. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality KAM-DIMATIA Series 2004-688 and ITI Series 2004-208. On the complexity of cake cutting KAM-DIMATIA Series 2004-695 and ITI Series 2004-216. On the Non-Learnability of a Single Spiking Neuron A lower bound for scheduling of unit jobs with immediate decision on parallel machines KAM-DIMATIA Series 2008-896 and ITI Series 2008-417 Optimal and online preemptive scheduling on uniformly related machines Online competitive algorithms for maximizing weighted throughput of unit jobs Online scheduling of equal-length jobs: Randomization and restarts help A sorting network in bounded arithmetic A Note on Scheduling Parallel Unit Jobs on Hypercubes. ITI Series 2008-418 The weighted 2-server problem Structured pigeonhole principle, search problems and hard tautologies Two algorithms for general list matrix partitions Bounded-depth Circuits: Separating Wires from Gates The greedy algorithm for the minimum common string partition problem Metamatematika teorií množin An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams Graph balancing: A special case of scheduling unrelated parallel machines Single source multiroute flows and cuts on uniform capacity networks Fragments of bounded arithmetic and the lengths of proofs Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity Substitution Frege and extended Frege proof systems in non-classical logics Approximate counting by hashing in bounded arithmetic Canonical Rules Optimal and online preemptive scheduling on uniformly related machines Preemptive Online Scheduling: Optimal Algorithms for All Speeds A note on scheduling parallel unit jobs on hypercubes Semi-online preemptive scheduling: one algorithm for all variants A lower bound for scheduling of unit jobs with immediate decision on parallel machines Algorithms for testing fault-tolerance of sequenced jobs Some applications of propositional logic to cellular automata String rewriting and proof complexity: an interpretation of resolution On convex complexity measures Abelian groups and quadratic residues in weak arithmetic

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software