Arranjos de subespacos, colapso de complexos simpliciais e complexidade computacional (1996)
- Authors:
- Autor USP: DONADELLI JUNIOR, JAIR - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.1996.tde-20210729-013117
- Subjects: CIÊNCIA DA COMPUTAÇÃO; TOPOLOGIA ALGÉBRICA; COMBINATÓRIA
- Language: Português
- Abstract: Neste trabalho descrevemos algumas aplicacoes da topologia algebrica em complexidade computacional. Bjorner e lovaz usaram metodos topologicos para estimar a altura de uma arvore de decisao linear que testa pertinencia em unioes finitas de poliedros convexos. Como aplicacoes eles obtiveram as cotas inferiores 'OMEGA' (n log(n/k)) para o problema dos k-iguais, 'OMEGA' (n log k) para o problema dos k-distintos e 'OMEGA' (n log(n/k)) para o problema de k-divisibilidade. Descrev emos tambem os metodos topologicos usados por kahn, saks e sturtevant para mostrar que propriedades de grafos de ordem potencia de primo sao evasivas. Estes mesmos metodos foram usados por yao para mostrar que propriedades de grafos bipartidos sao evasivas
- Imprenta:
- Data da defesa: 08.03.1996
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
DONADELLI JUNIOR, Jair. Arranjos de subespacos, colapso de complexos simpliciais e complexidade computacional. 1996. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1996. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013117/. Acesso em: 11 maio 2026. -
APA
Donadelli Junior, J. (1996). Arranjos de subespacos, colapso de complexos simpliciais e complexidade computacional (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013117/ -
NLM
Donadelli Junior J. Arranjos de subespacos, colapso de complexos simpliciais e complexidade computacional [Internet]. 1996 ;[citado 2026 maio 11 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013117/ -
Vancouver
Donadelli Junior J. Arranjos de subespacos, colapso de complexos simpliciais e complexidade computacional [Internet]. 1996 ;[citado 2026 maio 11 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013117/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
